• A: 12
• B: 16
• C: 6
• D: 19
• E: 18
• F: 2

Total: 73

import java.io.*
import java.util.*
import kotlin.math.*

fun main(){
	val f = BufferedReader(InputStreamReader(System.`in`))

	for(q in 1..f.readLine().toInt()){
		val n = f.readLine().toInt()
		val array = f.readLine().split(" ").map{it.toInt()}.toHashSet()

		if(array.size == 1){
			println(n)
		} else {
			println(1)
		}
	}
}

/*
Omkar orz
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class ModelPasswordA
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         while(T-->0)
         {
            int N = Integer.parseInt(infile.readLine());
            int[] arr = new int[N];
            st = new StringTokenizer(infile.readLine());
            for(int i=0; i < N; i++)
               arr[i] = Integer.parseInt(st.nextToken());
            int res = N;
            for(int i=1; i < N; i++)
               if(arr[i] != arr[i-1])
                  res = 1;
            sb.append(res+"\n");
         }
         System.out.print(sb);
      }
   }

#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

void solve() {
	int n; cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; ++i) {
		cin >> vec[i];
	}
	sort(all(vec));
	if (vec.front() == vec.back()) cout << n << "\n";
	else cout << "1\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int nbTests;
	cin >> nbTests;
	for (int iTest = 0; iTest < nbTests; ++iTest) {
		solve();
	}
}

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    val out = StringBuilder()
    for (c in 1..jin.readLine().toInt()) {
        val line = jin.readLine().split(" ")
        val n = line[0].toInt()
        val k = line[1].last().toString().toInt() % 2
        val array = jin.readLine().split(" ").map { it.toLong() }.toLongArray()
        var m = array.max()!!
        for (j in 0 until n) {
            array[j] = m - array[j]
        }
        if (k == 0) {
            m = array.max()!!
            for (j in 0 until n) {
                array[j] = m - array[j]
            }
        }
        out.appendln(array.joinToString(" "))
    }
    print(out)
}

//Omkar, Holy Light
import java.util.*;
import java.io.*;
import java.math.*;

   public class ModelB
   {
      public static void main(String omkar[]) throws Exception
      {
         //query based
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         while(T-->0)
         {
            st = new StringTokenizer(infile.readLine());
            int N = Integer.parseInt(st.nextToken());
            long K = Long.parseLong(st.nextToken())%2;
            if(K == 0)  K = 2;
            int[] arr = new int[N];
            st = new StringTokenizer(infile.readLine());
            for(int i=0; i < N; i++)
               arr[i] = Integer.parseInt(st.nextToken());
            for(int turns=0; turns < K; turns++)
            {
               int max = arr[0];
               for(int x: arr)
                  max = Math.max(max, x);
               for(int i=0; i < N; i++)
                  arr[i] = max-arr[i];
            }
            for(int i=0; i < N; i++)
            {
               sb.append(arr[i]);
               if(i+1 < N)
                  sb.append(" ");
            }
            sb.append("\n");
         }
         System.out.print(sb);
      }
   }

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int t;
	std::cin >> t;
	while(t--) {
		int n;
		long long k;
		std::cin >> n >> k;
		std::vector<int> a(n);
		for(int i = 0; i < n; i++) {
			std::cin >> a[i];
		}
		if(k > 1) {
			k = 2 + k % 2;
		}
		while(k--) {
			int mx = -1000000000;
			for(int i = 0; i < n; i++) {
				mx = std::max(mx, a[i]);
			}
			for(int i = 0; i < n; i++) {
				a[i] = mx - a[i];
			}
		}
		for(int i = 0; i < n; i++) {
			std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
		}
	}
}

import kotlin.math.max

fun main() {
    for (c in 1..readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val hs = readLine()!!.split(" ").map { it.toLong() }
        var answer = 0L
        for (j in 1 until n) {
            answer += max(0L, hs[j - 1] - hs[j])
        }
        println(answer)
    }
}

import java.util.*;
import java.io.*;

public class OmkarAndWaterslide {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(f.readLine());
        while(t-->0){
            int n = Integer.parseInt(f.readLine());
            long[] arr = new long[n];
            StringTokenizer st = new StringTokenizer(f.readLine());
            for(int i = 0; i < n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            long ans = 0;
            for(int i = 0; i < n-1; i++){
                ans+=Math.max(0, arr[i]-arr[i+1]);
            }
            out.println(ans);
        }
        out.close();
    }
}

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int t;
	std::cin >> t;
	while(t--) {
		int n;
		std::cin >> n;
		long long last = 0;
		long long ans = 0;
		while(n--) {
			long long x;
			std::cin >> x;
			x += ans;
			if(x >= last) {
				last = x;
			} else {
				ans += last &mdash; x;
			}
		}
		std::cout << ans << '\n';
	}
}

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    val out = StringBuilder()
    for (c in 1..jin.readLine().toInt()) {
        val n = jin.readLine().toInt()
        val s = jin.readLine()
        if (s.all { it == s[0] }) {
            out.appendln((n + 2) / 3)
        } else {
            var k = 0
            while (s[k] == s[0]) {
                k++
            }
            var answer = 0
            var curr = 0
            var chara = s[k]
            for (j in k until k + n) {
                if (s[j % n] == chara) {
                    curr++
                } else {
                    answer += curr / 3
                    curr = 1
                    chara = s[j % n]
                }
            }
            answer += curr / 3
            out.appendln(answer)
        }
    }
    print(out)
}

import java.util.*;
import java.io.*;

public class OmkarAndBedWars {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(f.readLine());
        while(t-->0){
            int n = Integer.parseInt(f.readLine());
            String str = f.readLine();
            boolean same = true;
            for(int i = 1; i < n; i++){
                if(str.charAt(i) != str.charAt(0)){
                    same = false;
                    break;
                }
            }
            if(same){
                out.println((n+2)/3);
                continue;
            }
            ArrayList<Integer> count = new ArrayList<Integer>();
            int last = 0;
            int cnt = 1;
            for(int i = 1; i < n; i++){
                if(str.charAt(i) == str.charAt(last)){
                    cnt++;
                }else{
                    count.add(cnt);
                    last = i;
                    cnt = 1;
                }
            }
            if(str.charAt(n-1) == str.charAt(0)){
                count.set(0, count.get(0)+cnt);
            }else{
                count.add(cnt);
            }
            int sum = 0;
            for(int i: count) sum+=(i/3);
            out.println(sum);

        }
        out.close();
    }

}

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, ans = 0;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    while(s.size() && s[0] == s.back()) {
        cnt++;
        s.pop_back();
    }
    if(s.empty()) {
        if(cnt <= 2) {
            cout << "0\n";
            return;
        }
        if(cnt == 3) {
            cout << "1\n";
            return;
        }
        cout << (cnt + 2) / 3 << '\n';
        return;
    }
    s.push_back('$');
    for(int i = 0; i + 1 < s.size(); i++) {
        cnt++;
        if(s[i] != s[i + 1]) {
            ans += cnt / 3;
            cnt = 0;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--)
        solve();
}

fun main() {
    val n = readLine()!!.toInt()
    for (x in 1..n) {
        for (y in 1..n) {
            if (x % 2 == 0) {
                print(1L shl (x + y))
            } else {
                print(0)
            }
            print(" ")
        }
        println()
    }
    val q = readLine()!!.toInt()
    for (j in 1..q) {
        val k = readLine()!!.toLong()
        var x = 1
        var y = 1
        print("1 1 ")
        for (e in 3..2 * n) {
            if ((x % 2 == 0) == (((k shr e) % 2L) == 1L)) {
                y++
            } else {
                x++
            }
            print("$x $y ")
        }
        println()
    }
}

//make sure to make new file!
import java.io.*;
import java.util.*;

public class DuckSolution{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      long[][] board = new long[n][n];
      board[0][0] = 0L;
      board[n-1][n-1] = 0L;
      
      for(int k = 0; k < n; k++){
         for(int j = 0; j < n; j++){
            if(k == 0 && j == 0) continue;
            if(k == n-1 && j == n-1) continue;
            
            if(k%2 == 0){
               board[k][j] = 1L << k+j;
            }
         }
      }
      
      for(int k = 0; k < n; k++){
         StringJoiner sj = new StringJoiner(" ");
         for(int j = 0; j < n; j++){
            sj.add("" + board[k][j]);
         }
         out.println(sj.toString());
      }
      
      out.flush();
      
      int q = Integer.parseInt(f.readLine());
      for(int t = 0; t < q; t++){
         long i = Long.parseLong(f.readLine());
         
         ArrayList<Integer> x = new ArrayList<Integer>();
         ArrayList<Integer> y = new ArrayList<Integer>();
         
         int curx = 0;
         int cury = 0;
         
         x.add(1);
         y.add(1);
         
         while(curx < n-1 || cury < n-1){
            if(curx == n-1){
               cury++;
            } else if(cury == n-1){
               curx++;
            } else {
               long and = Math.max(board[curx+1][cury],board[curx][cury+1]);
               if(((i & and) > 0) ^ (board[curx+1][cury] > 0)){
                  cury++;
               } else {
                  curx++;
               }
            
            
            }
            
            x.add(curx+1);
            y.add(cury+1);
         }
         
         StringJoiner sj = new StringJoiner(" ");
         for(int k = 0; k < x.size(); k++){
            sj.add("" + x.get(k) + " " + y.get(k));
         }
         out.println(sj.toString());
         out.flush();
      }
      
      
      
      
      
      
      
      
      out.close();
   }
   
      
}

#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int side; cin >> side;
	vector<vector<ll>> grid(side, vector<ll>(side, 0));
	for (int i = 0; i < side; ++i) {
		for (int j = 0; j < side; ++j) {
			if ((i-j+side)&2LL) grid[i][j] = (1LL << (i+j));
			cout << grid[i][j] << " \n"[j==side-1];
		}
	}
	cout << flush;
	int nbQuery; cin >> nbQuery;
	for (int iQuery = 0; iQuery < nbQuery; ++iQuery) {
		ll sum; cin >> sum;
		cout << "1 1";
		int row = 0, col = 0;
		for (int diag = 0; diag < 2*side-2; ++diag) {
			ll should = sum&(1LL<<(diag+1));
			if (row+1<side && grid[row+1][col] == should) ++row;
			else ++col;
			cout << " " << row+1 << " " << col+1;
		}
		cout << endl << flush;
	}
}

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    val n = jin.readLine().toLong()
    val tokenizer = StringTokenizer(jin.readLine())
    var sum = 0L
    for (j in 0L until n) {
        sum += tokenizer.nextToken().toLong() - j
    }
    val joiner = StringJoiner(" ")
    for (j in 0L until n) {
        joiner.add(((sum / n) + (if (j < sum % n) 1L else 0L) + j).toString())
    }
    println(joiner)
}

import java.util.*;
import java.io.*;

public class OmkarAndLandslideNumber2 {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        long n = Long.parseLong(f.readLine());
        long sum = 0;
        StringTokenizer st = new StringTokenizer(f.readLine());
        for(int i = 0; i < n; i++){
            sum+=Long.parseLong(st.nextToken());
        }
        long k = ((sum - n*(n - 1)/2) / n);
        long diff = sum - (n*k + n*(n - 1)/2);
        StringBuilder ans = new StringBuilder();
        for(long i = 0; i < n; i++){
            if(i < diff){
                ans.append(k+i+1L);
                ans.append(" ");
            }else{
                ans.append(k+i);
                ans.append(" ");
            }
        }
        out.println(ans.toString().trim());
        out.close();
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	ll n;
	cin >> n;
	ll s = 0;
	for (ll x, i = 0; i < n; ++i)
		cin >> x, s += x;

	ll l = (s - n * (n-1) / 2) / n + 1;
	s = l * n + n * (n-1) / 2 - s;
	for (int i = 0; i < n; ++i)
		cout << l + i - (n-i <= s) << " \n"[i+1==n];

	return 0;
}

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
import kotlin.math.min

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    var line = jin.readLine().split(" ")
    val n = line[0].toInt()
    val m = line[1].toInt()
    val k = line[2].toInt()
    val dpLeft = IntArray(1 shl k) { n + 1 }
    val dpRight = IntArray(1 shl k) { -1 }
    var original = jin.readLine().reversed().toInt(2)
    var goal = jin.readLine().reversed().toInt(2)
    val permutation = IntArray(k) { it }
    dpLeft[original] = 0
    dpRight[goal] = 0
    for (j in 1..n) {
        line = jin.readLine().split(" ")
        val a = line[0].toInt() - 1
        val b = line[1].toInt() - 1
        var c = (original shr permutation[a]) and 1
        var d = (original shr permutation[b]) and 1
        original -= c shl permutation[a]
        original -= d shl permutation[b]
        original += d shl permutation[a]
        original += c shl permutation[b]
        c = (goal shr permutation[a]) and 1
        d = (goal shr permutation[b]) and 1
        goal -= c shl permutation[a]
        goal -= d shl permutation[b]
        goal += d shl permutation[a]
        goal += c shl permutation[b]
        dpLeft[original] = min(dpLeft[original], j)
        dpRight[goal] = j
        c = permutation[a]
        d = permutation[b]
        permutation[a] = d
        permutation[b] = c
    }
    var best = -1
    var l = -1
    var r = -1
    for (mask in (1 shl k) - 1 downTo 0) {
        for (e in 0 until k) {
            if ((mask shr e) and 1 != 0) {
                dpLeft[mask - (1 shl e)] = min(dpLeft[mask - (1 shl e)], dpLeft[mask])
                dpRight[mask - (1 shl e)] = max(dpRight[mask - (1 shl e)], dpRight[mask])
            }
        }
        if (dpLeft[mask] + m <= dpRight[mask] && Integer.bitCount(mask) > best) {
            best = Integer.bitCount(mask)
            l = dpLeft[mask] + 1
            r = dpRight[mask]
        }
    }
    println(k - Integer.bitCount(original) - Integer.bitCount(goal) + (2 * best))
    println("$l $r")
}

import java.io.*;
import java.util.*;

public class OmkarAndPies {
    public static int INF = Integer.MAX_VALUE/2;
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int bitstr = Integer.parseInt(f.readLine(), 2);
        int goal = Integer.parseInt(f.readLine(), 2);
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(f.readLine());
            arr1[i] = Integer.parseInt(st.nextToken());
            arr2[i] = Integer.parseInt(st.nextToken());
        }
        int[] lefts = new int[n+1];
        int[] rights = new int[n+1];
        rights[0] = goal;
        lefts[0] = bitstr;
        int[] permutation = new int[k];
        int[] indices = new int[k];
        for(int i = 0; i < k; i++){
            permutation[i] = i;
            indices[i] = i;
        }
        for(int i = 0; i < n; i++){
            int temp = indices[arr1[i]-1];
            indices[arr1[i]-1] = indices[arr2[i]-1];
            indices[arr2[i]-1] = temp;
            permutation[indices[arr1[i]-1]] = arr1[i]-1;
            permutation[indices[arr2[i]-1]] = arr2[i]-1;
            lefts[i+1] = applyPermutation(indices, bitstr, k);
            rights[i+1] = applyPermutation(indices, goal, k);
        }
        int[] dpLeft = new int[(1 << k)];
        int[] dpRight = new int[(1 << k)];
        Arrays.fill(dpLeft, INF);
        Arrays.fill(dpRight, -INF);
        for(int i = 0; i <= n; i++){
            dpLeft[lefts[i]] = Math.min(dpLeft[lefts[i]], i);
            dpRight[rights[i]] = Math.max(dpRight[rights[i]], i);
        }
        for(int i = (1 << k)-1; i > 1; i--){
            int temp = i;
            int count = 0;
            while(temp != 0){
                if(temp % 2 == 1){
                    dpLeft[i-(1 << count)] = Math.min(dpLeft[i-(1 << count)], dpLeft[i]);
                    dpRight[i-(1 << count)] = Math.max(dpRight[i-(1 << count)], dpRight[i]);
                }
                temp/=2;
                count++;
            }
        }
        for(int i = 0; i < (1 << k); i++){
            if(dpLeft[i] == 2 && dpRight[i] == 8){
                System.out.println(i);
            }
        }
        int maxVal = -INF;
        int intLeft = -1;
        int intRight = -1;
        for(int i = 0; i < (1 << k); i++){
            if(dpRight[i]-dpLeft[i] < m) continue;
            int a1 = lefts[dpLeft[i]];
            int a2 = rights[dpRight[i]];
            int count = 0;
            for(int j = 0; j < k; j++){
                if(a1 % 2 == a2 % 2) count++;
                a1/=2;
                a2/=2;
            }
            if(count > maxVal){
                maxVal = count;
                intLeft = dpLeft[i]+1;
                intRight = dpRight[i];
            }
        }
        out.println(maxVal);
        out.println(intLeft + " " + intRight);
        out.close();


    }
    public static int applyPermutation(int[] permutation, int bitstr, int k){
        int ans = 0;
        for(int i = k-1; i >= 0; i--){
           if(bitstr % 2 == 1){
               ans += (1 << (k-permutation[i]-1));
           }
           bitstr/=2;
        }
        return ans;
    }
}

#include <bits/stdc++.h>
using namespace std;
int p[20],dp[2][(1<<20)];
int getmask(string s)
{
	int ans=0;
	for (int i=0;i<s.size();i++)
	ans|=((s[i]-'0')<<i);
	return ans;
}
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	string a,b;
	cin >> a >> b;
	for (int i=0;i<k;i++)
	p[i]=i;
	for (int i=0;i<(1<<k);i++)
	{
		dp[0][i]=1e9;
		dp[1][i]=-1e9;
	}
	dp[0][getmask(a)]=0;
	dp[1][getmask(b)]=0;
	for (int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x--;
		y--;
		swap(p[x],p[y]);
		string aa(k,'0'),bb(k,'0');
		for (int j=0;j<k;j++)
		{
			aa[p[j]]=a[j];
			bb[p[j]]=b[j];
		}
		dp[0][getmask(aa)]=min(dp[0][getmask(aa)],i);
		dp[1][getmask(bb)]=i;
	}
	int o1=count(a.begin(),a.end(),'1'),o2=count(b.begin(),b.end(),'1');
	pair<int,pair<int,int> > ans(0,{0,0});
	for (int i=(1<<k)-1;i>=0;i--)
	{
		if (dp[1][i]-dp[0][i]>=m)
		ans=max(ans,make_pair(k-(o1+o2-2*__builtin_popcount(i)),make_pair(dp[0][i]+1,dp[1][i])));
		for (int j=0;j<k;j++)
		{
			if (i&(1<<j))
			{
				dp[0][i^(1<<j)]=min(dp[0][i^(1<<j)],dp[0][i]);
				dp[1][i^(1<<j)]=max(dp[1][i^(1<<j)],dp[1][i]);
			}
		}
	}
	printf("%d\n%d %d",ans.first,ans.second.first,ans.second.second);
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int MOD = 998244353;

vector<int> fact;
vector<int> ifact;
vector<int> pow2;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
void radd(int &a, int b)
{
	a=add(a,b); 
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
void rmult(int &a, int b)
{
	a=mult(a,b);
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<0) return 0;
	if(b<0) return 0;
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
}
	
int solve_slow(int n, int m)
{
	vi f(n+1,0);
	for(int k=1;k<=n;k++)
	{
		int sum=0;
		for(int l=1;l<=k;l++)
		{
			for(int i=0;i<=n;i++)
			{
				int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
				radd(sum, mult(coeff, add(f[k-l],i+1)));
			}
		}
		{
			int l=0;
			int sumcoeff=0;
			for(int i=0;i<=n;i++)
			{
				int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
				radd(sum, mult(coeff, i+1));
				radd(sumcoeff,coeff);
			}
			int actualcoeff = add(1,MOD-sumcoeff);
			assert(actualcoeff!=0);
			f[k]=mult(inverse(actualcoeff),sum);
		}
	}
	return f[n];
}

int solve_fast(int n, int m)
{
	vi f(n+1,0);
	int presum=0;
	for(int k=1;k<=n;k++)
	{
		int sum=mult(presum,choose(n+m,m+k));
		radd(sum,mult(fact[m-1],mult(choose(m+k+1,m+1),choose(n+m+1,m+k+1))));
		int outsidecoeff = mult(fact[k],mult(fact[n-k],mult(ifact[n+m],m)));
		sum = mult(sum, outsidecoeff);
		f[k]=mult(mult(m+k,mult(ifact[k],fact[k-1])),sum);
		//f[k]=mult(mult(k,mult(fact[m+k-1],ifact[m+k])),sum);
		radd(presum,mult(fact[m+k-1],mult(ifact[k],f[k])));
	}
	return f[n];
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(int(1e7)+100);
	int n,m; cin>>n>>m;
	//cout<<solve_slow(n,m)<<'\n';
	cout<<solve_fast(n,m)<<'\n';
}

import java.util.*;
import java.io.*;

public class ZSShufflesCards {
    public static long MOD = 998244353;
    public static long[] fact;
    public static long[] invfact;
    public static long[] pow2;
    public static int MAX = 4000005;
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        fact = new long[MAX];
        invfact = new long[MAX];
        pow2 = new long[MAX];
        fact[0] = 1;
        invfact[0] = 1;
        pow2[0] = 1;
        for(int i = 1; i < MAX; i++){
            pow2[i] = add(pow2[i-1], pow2[i-1]);
            fact[i] = mult(fact[i-1], i);
        }
        invfact[MAX-1] = inverse(fact[MAX-1]);
        for(int i = MAX-2; i >= 1; i--){
            invfact[i] = mult(invfact[i+1], i+1);
        }
        long[] ans = new long[n+1];
        long currsum = 0;
        for(int k = 1; k <= n; k++){
            long sum = mult(currsum, ncr(n+m, m+k));
            sum = add(sum,mult(fact[m-1],mult(ncr(m+k+1,m+1),ncr(n+m+1,m+k+1))));
            long outsidecoeff = mult(fact[k],mult(fact[n-k],mult(invfact[n+m],m)));
            sum = mult(sum, outsidecoeff);
            ans[k]=mult(mult(m+k,mult(invfact[k],fact[k-1])),sum);
            currsum = add(currsum,mult(fact[m+k-1],mult(invfact[k],ans[k])));
        }
        out.println(ans[n]);
        out.close();

    }
    public static long add(long a, long b){
        return((a+b)%MOD+MOD)%MOD;
    }
    public static long mult(long a, long b){
        return((a*b)%MOD+MOD)%MOD;
    }
    public static long pow(long a, long b){
        long ans = 1;
        while(b > 0){
            if((b&1) == 1) ans = mult(ans, a);
            a = mult(a, a);
            b>>=1;
        }
        return ans;
    }
    public static long ncr(long a, long b){
        if(a<0) return 0;
        if(b<0) return 0;
        if(a<b) return 0;
        if(b==0) return 1;
        if(a==b) return 1;
        return mult(fact[(int)a],mult(invfact[(int)b],invfact[(int)(a-b)]));
    }
    public static long inverse(long a){
        return pow(a, MOD-2);
    }
}

const val MOD = 998244353L

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val factorial = LongArray(4000002)
    factorial[0] = 1L
    for (j in 1..4000001) {
        factorial[j] = (j.toLong() * factorial[j - 1]) % MOD
    }
    val factInv = LongArray(4000002)
    factInv[4000001] = factorial[4000001] pow -1
    for (j in 4000000 downTo 0) {
        factInv[j] = ((j + 1).toLong() * factInv[j + 1]) % MOD
    }
    fun choose(a: Int, b: Int) = if (a < 0 || b < 0 || b > a) 0L else (factorial[a] * ((factInv[b] * factInv[a - b]) % MOD)) % MOD
    val answer = LongArray(n + 1)
    var currSum = 0L
    for (k in 1..n) {
        var sum = currSum * choose(n + m, m + k)
        sum %= MOD
        sum += factorial[m - 1] * ((choose(m + k + 1, m + 1) * choose(n + m + 1, m + k + 1)) % MOD)
        sum %= MOD
        sum *= (factorial[k] * ((factorial[n - k] * ((factInv[n + m] * m.toLong()) % MOD)) % MOD)) % MOD
        sum %= MOD
        answer[k] = sum * (((m + k).toLong() * ((factInv[k] * factorial[k - 1]) % MOD)) % MOD)
        answer[k] %= MOD
        currSum += factorial[m + k - 1] * ((factInv[k] * answer[k]) % MOD)
        currSum %= MOD
    }
    println(answer[n])
}

const val MOD_TOTIENT = MOD.toInt() - 1

infix fun Long.pow(power: Int): Long {
    var e = power
    e %= MOD_TOTIENT
    if (e < 0) {
        e += MOD_TOTIENT
    }
    if (e == 0 && this == 0L) {
        return this
    }
    var b = this % MOD
    var res = 1L
    while (e > 0) {
        if (e and 1 != 0) {
            res *= b
            res %= MOD
        }
        b *= b
        b %= MOD
        e = e shr 1
    }
    return res
}

#include<bits/stdc++.h>

using namespace std;
#define MAX 262144
#define MAXN 1000000
long long int a[MAXN],b[MAXN];


using cd = complex<double>;
const double PI = acos(-1);
vector<cd> A(MAX),B(MAX);
vector<cd> Amx(MAX),Bmx(MAX);
vector<cd> Amn(MAX),Bmn(MAX);
vector<cd> E11(MAX),E12(MAX),E21(MAX),E22(MAX);
vector<cd> SQ1(MAX),SQ2(MAX);
vector<cd> V(MAX);
vector<long long int> A1(MAX),A2(MAX);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}
void prod(vector<cd> &a, vector<cd> &b, vector<cd> &c){
  for(int i=0;i<a.size();i++){
    c[i]=a[i]*b[i];
  }
}

int main(){
  long long int n,m,q;
  scanf("%lld %lld %lld",&n,&m,&q);
  
  for(int i=0;i<n;i++){
    scanf("%lld",&a[i]);
  }
  for(int i=0;i<m;i++){
    scanf("%lld",&b[i]);
  }
  for(int i=0;i<MAX;i++){
    A[i]=cd(0,0);
    Amn[i]=cd(0,0);
    Amx[i]=cd(0,0);
    B[i]=cd(0,0);
    Bmn[i]=cd(0,0);
    Bmx[i]=cd(0,0);
  }
  for(int i=0;i<n;i++){
    A[a[i]]+=cd(1,0);
  }
  for(int i=0;i<n-1;i++){
    Amn[min(a[i],a[i+1])]+=cd(1,0);
  }
  for(int i=0;i<n-1;i++){
    Amx[max(a[i],a[i+1])]+=cd(1,0);
  }
  for(int i=0;i<m;i++){
    B[b[i]]+=cd(1,0);
  }
  for(int i=0;i<m-1;i++){
    Bmn[min(b[i],b[i+1])]+=cd(1,0);
  }
  for(int i=0;i<m-1;i++){
    Bmx[max(b[i],b[i+1])]+=cd(1,0);
  }
  
  fft(A,0);
  fft(Amn,0);
  fft(Amx,0);
  fft(B,0);
  fft(Bmn,0);
  fft(Bmx,0);
  prod(A,Bmn,E11);
  prod(Amn,B,E12);
  prod(Amx,B,E21);
  prod(A,Bmx,E22);
  prod(Amn,Bmn,SQ1);
  prod(Amx,Bmx,SQ2);
  prod(A,B,V);
  fft(E11,1);
  fft(E12,1);
  fft(E21,1);
  fft(E22,1);
  fft(SQ1,1);
  fft(SQ2,1);
  fft(V,1);
  for(int i=0;i<MAX;i++){
    A1[i]=round(SQ1[i].real())-round(E11[i].real())-round(E12[i].real())+round(V[i].real());
    A2[i]=round(SQ2[i].real())-round(E21[i].real())-round(E22[i].real())+round(V[i].real());
  }
  for(int i=1;i<MAX;i++){
    A2[i]+=A2[i-1];
  }
  for(int i=MAX-2;i>-1;i--){
    A1[i]+=A1[i+1];
  }
  for(int i=0;i<q;i++){
    int query;
    scanf("%d",&query);
    //cout<<A1[query]<<" "<<A2[query-1]<<endl;
    printf("%lld\n",A1[query]-A2[query-1]);
  }
  return 0;
}