Problem Statement

We have N coins numbered 1 to N with two distinguishable sides. A string S represents the current state of the coins. If the i-th character of S is 1, coin i is showing heads; if that character is 0, coin i is showing tails.

You can repeat the following operation zero or more times.

• Choose a pair of integers (i,j) such that 1\leq i < j\leq N and j-i\geq \bm{2}. Flip coin i and coin j.

Determine whether it is possible to make all the N coins show tails. If it is possible, find the minimum number of operations needed.

You are given T test cases to solve.

Constraints

• 1 \leq T \leq 2\times 10^5
• 3 \leq N \leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• All numbers in the input are integers.
• For each input file, the sum of N over the test cases is at most 2\times 10^5.

Sample Input 1

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

Sample Output 1

1
2
-1
0
8

For the first test case, you can perform the operation with (i,j)=(1,3) to make all the coins show tails in one operation.

For the second test case, you can perform the operation with (i,j)=(1,3) and then with (i,j)=(4,6) to make all the coins show tails in two operations.

For the third test case, you can prove that there is no way to make all the coins show tails, so you should print -1.

For the fourth test case, the coins already show tails, so no operation is needed.

Problem Statement

For a finite multiset S of non-negative integers, let us define \mathrm{mex}(S) as the smallest non-negative integer not in S. For instance, \mathrm{mex}(\lbrace 0,0, 1,3\rbrace ) = 2, \mathrm{mex}(\lbrace 1 \rbrace) = 0, \mathrm{mex}(\lbrace \rbrace) = 0.

There are N non-negative integers on a blackboard. The i-th integer is A_i.

You will perform the following operation exactly K times.

• Choose zero or more integers on the blackboard. Let S be the multiset of chosen integers, and write \mathrm{mex}(S) on the blackboard once.

How many multisets can be the multiset of integers on the final blackboard? Find this count modulo 998244353.

Constraints

• 1 \leq N,K \leq 2\times 10^5
• 0\leq A_i\leq 2\times 10^5
• All numbers in the input are integers.

Sample Input 1

3 1
0 1 3

Sample Output 1

3

The following three multisets can be obtained by the operations.

• \lbrace 0,0,1,3 \rbrace
• \lbrace 0,1,1,3\rbrace
• \lbrace 0,1,2,3 \rbrace

For instance, you can get \lbrace 0,1,1,3\rbrace by choosing the 0 on the blackboard to let S=\lbrace 0\rbrace in the operation.

Sample Input 2

2 1
0 0

Sample Output 2

2

The following two multisets can be obtained by the operations.

• \lbrace 0,0,0 \rbrace
• \lbrace 0,0,1\rbrace

Note that you may choose zero integers in the operation.

Sample Input 3

5 10
3 1 4 1 5

Sample Output 3

7109

Problem Statement

We have a tree T with vertices numbered 1 to N. The i-th edge of T connects vertex u_i and vertex v_i.

Let us use T to define the similarity of a permutation P = (P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) as follows.

• For a simple path x=(x_1,x_2,\ldots,x_k) in T, let y=(P_{x_1}, P_{x_2},\ldots,P_{x_k}). The similarity is the maximum possible length of a longest common subsequence of x and y.

Construct a permutation P with the minimum similarity.

Constraints

• 2 \leq N \leq 5000
• 1\leq u_i,v_i\leq N
• The given graph is a tree.
• All numbers in the input are integers.

Sample Input 1

3
1 2
2 3

Sample Output 1

3 2 1

This permutation has a similarity of 1, which can be computed as follows.

• For x=(1), we have y=(P_1)=(3). The length of a longest common subsequence of x and y is 0.

• For x=(2), we have y=(P_2)=(2). The length of a longest common subsequence of x and y is 1.

• For x=(3), we have y=(P_2)=(1). The length of a longest common subsequence of x and y is 0.

• For x=(1,2), we have y=(P_1,P_2)=(3,2). The length of a longest common subsequence of x and y is 1. The same goes for x=(2,1), the reversal of (1,2).

• For x=(2,3), we have y=(P_2,P_3)=(2,1). The length of a longest common subsequence of x and y is 1. The same goes for x=(3,2), the reversal of (2,3).

• For x=(1,2,3), we have y=(P_1,P_2,P_3)=(3,2,1). The length of a longest common subsequence of x and y is 1. The same goes for x=(3,2,1), the reversal of (1,2,3).

We can prove that no permutation has a similarity of 0 or less, so this permutation is a valid answer.

Sample Input 2

4
2 1
2 3
2 4

Sample Output 2

3 4 1 2

If multiple permutations have the minimum similarity, you may print any of them. For instance, you may also print 4 3 2 1.

Problem Statement

You are given a sequence of N non-negative integers A=(A_1,A_2,\dots,A_N) and a positive integer K.

Find the bitwise \mathrm{XOR} of \displaystyle \sum_{i=1}^{K} A_{X_i} over all N^K sequences of K positive integer sequences X=(X_1,X_2,\dots,X_K) such that 1 \leq X_i \leq N\ (1\leq i \leq K).

Constraints

• 1 \leq N \leq 1000
• 1 \leq K \leq 10^{12}
• 0 \leq A_i \leq 1000
• All values in the input are integers.

Sample Input 1

2 2
10 30

Sample Output 1

40

There are four sequences to consider: (X_1,X_2)=(1,1),(1,2),(2,1),(2,2), for which A_{X_1}+A_{X_2} is 20,40,40,60, respectively. Thus, the answer is 20 \oplus 40 \oplus 40 \oplus 60=40.

Sample Input 2

4 10
0 0 0 0

Sample Output 2

0

Sample Input 3

11 998244353
314 159 265 358 979 323 846 264 338 327 950

Sample Output 3

236500026047

Problem Statement

Find the number, modulo 998244353, of good sequences of length N whose elements are integers between 0 and M, inclusive, and whose sum is at most K.

Here, a length-N sequence X=(X_1,X_2,\ldots,X_N) is said to be good if and only if there is a graph G that satisfies all of the following conditions.

• G is a graph with N vertices numbered 1 to N without self-loops. (It may have multi-edges.)
• For each i\ (1\leq i \leq N), the degree of vertex i is X_i.
• For each i\ (1\leq i \leq N), no edge connects vertex i and vertex i+1. Here, vertex N+1 means vertex 1.

Constraints

• 4 \leq N \leq 3000
• 0 \leq M \leq 3000
• 0\leq K \leq NM
• All numbers in the input are integers.

Sample Input 1

4 1 2

Sample Output 1

3

The following three sequences are good.

• (0,0,0,0)
• (0,1,0,1)
• (1,0,1,0)

Sample Input 2

10 0 0

Sample Output 2

1

Sample Input 3

314 159 26535

Sample Output 3

248950743

Print the count modulo 998244353.

Problem Statement

You are given three integer sequences of length N: A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N),C=(C_1,C_2,\dots,C_N).

Find one set of integers that satisfies the following conditions.

• It can be obtained as follows: start with an empty set, and for each i=1,2,\dots,N in this order, add A_i or B_i to the set.
• It can be obtained as follows: start with an empty set, and for each i=1,2,\dots,N in this order, add A_i or C_i to the set.
• It has the maximum number of elements among the sets that satisfy the two conditions above.

Constraints

• 1 \leq N \leq 5000
• 1 \leq A_i,B_i,C_i \leq 10000
• All values in the input are integers.

Sample Input 1

3
1 1 1
2 3 4
5 4 2

Sample Output 1

3
4 1 2

For the set \lbrace 1,2,4\rbrace, we have the following.

• The first condition is satisfied because you can add B_1,A_2,B_3 to an empty set to obtain this set.
• The second condition is satisfied because you can add A_1,C_2,C_3 to an empty set to obtain this set.

Clearly, any set satisfying these conditions has at most N=3 elements, so this set also satisfies the third condition.

Sample Input 2

15
1 1 15 11 13 7 7 1 6 1 5 7 4 9 8
11 30 1 18 16 15 19 17 3 27 22 7 21 29 9
24 14 23 17 18 16 9 12 10 5 26 29 20 19 11

Sample Output 2

12
7 9 11 17 19 1 15 4 5 6 29 13