Problem Statement

(In this problem statement, all sequences consist of non-negative integers.)

There is a blackboard on which sequences are written. Initially, the blackboard only has one length-N sequence A=(A_1,A_2,\dots,A_N).

We repeat the following operation until all sequences on the blackboard are of length 1:

• Among the sequences on the blackboard, choose one that has length at least 2, and remove it from the blackboard. Let the chosen sequence be B=(B_1,B_2,\dots,B_n). Then, choose an integer k satisfying 1 \leq k < n, and define X = B_1 \oplus B_2 \oplus \dots \oplus B_k and Y=B_{k+1} \oplus B_{k+2} \oplus \dots \oplus B_n. Finally, write two sequences (B_1 \oplus Y, B_2 \oplus Y,\dots,B_k \oplus Y) and (B_{k+1} \oplus X,\ B_{k+2} \oplus X,\dots,B_n \oplus X) on the blackboard.

Here, \oplus denotes the bitwise \mathrm{XOR} operation.

After this series of operations, let (C_1),(C_2),\dots,(C_N) be the N sequences of length 1 on the blackboard. Find the minimum possible value of \sum_{i=1}^{N} C_i.

Constraints

• 1 \leq N \leq 500
• 0 \leq A_i < 2^{40}
• All input values are integers.

Sample Input 1

4
1 3 4 5

Sample Output 1

6

Initially, the blackboard has (1,3,4,5) written on it. From here, we perform operations in the following steps.

1. Remove (1,3,4,5) from the blackboard and set k=2. Then, X=1 \oplus 3=2 and Y=4 \oplus 5=1, and two new sequences (1 \oplus 1, 3 \oplus 1)=(0,2) and (4 \oplus 2, 5 \oplus 2)=(6,7) are written on the blackboard.
2. Remove (0,2) from the blackboard and set k=1. Two new sequences (2),(2) are written on the blackboard.
3. Remove (6,7) from the blackboard and set k=1. Two new sequences (1),(1) are written on the blackboard.

After these steps, the four sequences on the blackboard are (2),(2),(1),(1), each of length 1. Their sum is 2+2+1+1=6.

Sample Input 2

7
1 5 14 23 20 18 20

Sample Output 2

39

Sample Input 3

20
246260893965 450834729933 1091503137264 661761201979 238822689279 375606126051 183045127603 1004516515418 976478741401 957665143474 451659136716 828528157302 204109014940 184065081345 122138832666 130646707415 144391522538 87966805947 381909891703 343575641318

Sample Output 3

3597854777632

Problem Statement

You are given integers N, K, and a correct bracket sequence S of length K consisting of ( and ).

Find the number, modulo 998244353, of length-N strings T consisting of ( and ) that satisfy all of the following conditions:

• There exists a (not necessarily contiguous) subsequence of T that is a correct bracket sequence of length K.
• Among all (not necessarily contiguous) subsequences of T that are correct bracket sequences of length K, the lexicographically largest one is S.

Here, concerning the lexicographical order of strings consisting of ( and ), we consider ( smaller than ).

Constraints

• K \leq N \leq 10^7
• 2 \leq K \leq 5 \times 10^5
• N and K are integers.
• S is a correct bracket sequence of length K.

Sample Input 1

7 4
(())

Sample Output 1

20

For example, if T=((()))), the only (not necessarily contiguous) subsequence of T that is a correct bracket sequence of length 4 is (()), which equals S, so it satisfies the conditions.

If T=((())(), there are two (not necessarily contiguous) subsequences of T that are correct bracket sequences of length 4: ()() and (()). The lexicographically largest one is ()(), so it does not satisfy the conditions.

Sample Input 2

20 4
()()

Sample Output 2

1047225

Sample Input 3

71 10
()(()())()

Sample Output 3

190654464

Sample Input 4

10000000 28
(()()(()))(()((()))())()(())

Sample Output 4

769035381

Problem Statement

There is a simple connected undirected graph G with N vertices and M edges, where the vertices are labeled 1,2,\dots,N. The i-th edge connects two vertices u_i and v_i.

Determine whether there exists a length-N sequence of non-negative integers X=(X_1,X_2,\dots,X_N) that satisfies all of the following conditions:

• X_v does not exceed the degree of vertex v in G for each v=1,2,\dots,N.
• There is no directed graph obtained by assigning directions to the M edges of G in which, for each v=1,2,\dots,N, either the in-degree or the out-degree of v equals X_v.

You have T test cases; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• All input values are integers.
• The graph G given in the input is a simple connected undirected graph.
• The sum of N over all test cases in each input is at most 2 \times 10^5.
• The sum of M over all test cases in each input is at most 2 \times 10^5.

Sample Input 1

3
4 4
1 2
2 3
3 4
4 1
7 6
3 4
3 6
2 5
1 2
1 3
2 7
15 20
11 13
11 7
12 6
5 2
4 1
15 3
9 8
13 5
8 6
7 5
11 8
12 9
14 1
1 11
6 7
1 3
2 3
3 7
5 12
10 6

Sample Output 1

Yes
No
Yes

In the first test case, for example, X=(2,2,2,1) satisfies the conditions.

In the second test case, no sequence X satisfies the conditions.

Problem Statement

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

A is a monotonically non-decreasing sequence. That is, A_i \leq A_{i+1} holds for all i = 1, 2, \dots, N - 1.

We call a length-N sequence of non-negative integers X = (X_1, X_2, \dots, X_N) a "good sequence" if X is monotonically non-decreasing and one can make all elements of X equal to 0 by applying the following operation zero or more times:

• Choose an integer i such that 1 \leq i \leq N - K + 1. Let S = X_i + X_{i+1} + \dots + X_{i+K-1}. Replace each of the i-th through (i+K-1)-th elements of X with \left\lfloor \frac{S}{K} \right\rfloor.

Find the maximum possible value of \sum_{i=1}^N B_i for a sequence of non-negative integers B = (B_1, B_2, \dots, B_N) that satisfy all of the following conditions:

• B_i \leq A_i holds for all i = 1, 2, \dots, N.
• B is a monotonically non-decreasing sequence and is a "good sequence."

You have T test cases; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq K \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^{9}
• A_i \leq A_{i+1} holds for all i = 1, 2, \dots, N - 1.
• All input values are integers.
• The sum of N over all test cases in one input is at most 2 \times 10^5.

Sample Input 1

4
4 2
0 1 2 3
4 3
0 1 2 3
20 5
1 2 3 3 4 5 6 7 7 8 9 9 11 13 14 16 16 17 18 19
20 10
36410986 135774405 160873759 200077345 386257217 408140905 426675713 448759426 470780343 572969565 653981029 693304642 741916215 764524315 768298046 811893935 840607643 847634785 856942510 883746061

Sample Output 1

6
5
185
739

In the first test case, A itself is a "good sequence." For example, we can make all elements of A equal to 0 with the following steps:

1. Let i=3. Then, S=A_3+A_4=5. Replace A_3 and A_4 with \left\lfloor \frac{5}{2} \right\rfloor = 2, resulting in A=(0,1,2,2).
2. Let i=2. Then, S=A_2+A_3=3. Replace A_2 and A_3 with \left\lfloor \frac{3}{2} \right\rfloor = 1, resulting in A=(0,1,1,2).
3. Let i=3. Then, S=A_3+A_4=3. Replace A_3 and A_4 with \left\lfloor \frac{3}{2} \right\rfloor = 1, resulting in A=(0,1,1,1).
4. Let i=1. Then, S=A_1+A_2=1. Replace A_1 and A_2 with \left\lfloor \frac{1}{2} \right\rfloor = 0, resulting in A=(0,0,1,1).
5. Let i=2. Then, S=A_2+A_3=1. Replace A_2 and A_3 with \left\lfloor \frac{1}{2} \right\rfloor = 0, resulting in A=(0,0,0,1).
6. Let i=3. Then, S=A_3+A_4=1. Replace A_3 and A_4 with \left\lfloor \frac{1}{2} \right\rfloor = 0, resulting in A=(0,0,0,0).

Thus, taking B = A achieves the maximum sum 0+1+2+3=6.

In the second test case, A is not a "good sequence." However, if we take B = (0,0,2,3), then B is a "good sequence" and satisfies the conditions.

Problem Statement

For a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), define a length-N integer sequence f(P) as follows.

• Initialize an integer sequence X with X=(P_1,P_2,\dots,P_N). Repeat the following operation until X is a strictly increasing sequence. (It can be shown that X will be a strictly increasing sequence in a finite number of operations for any permutation P.)

  • Let k be the smallest index i (1 \leq i < N) such that X_i > X_{i+1}. Move the k-th element of X to the end. More precisely, replace X with (X_1,X_2,\dots,X_{k-1},X_{k+1},X_{k+2},\dots,X_N,X_{k}).

  Let C_x be the number of times an integer x is moved to the end during this series of operations. Then, define f(P)=(C_1,C_2,\dots,C_N).

Find the number, modulo a prime number M, of distinct sequences that can occur as f(P).

Constraints

• 1 \leq N \leq 500
• 10^8 \leq M \leq 10^9
• M is prime.
• All input values are integers.

Sample Input 1

4 998244353

Sample Output 1

8

For example, when P=(1,4,3,2), we initialize X=(1,4,3,2) and perform operations as follows:

1. Since X_1 \leq X_2 but X_2 > X_3, the element X_2=4 is moved to the end, and X becomes (1,3,2,4).
2. X_2=3 is moved to the end, and X becomes (1,2,4,3).
3. X_3=4 is moved to the end, and X becomes (1,2,3,4).

The number of times 1,2,3,4 are moved to the end is 0,0,1,2, respectively, so f(P)=(0,0,1,2).

Sample Input 2

71 998244353

Sample Output 2

473972314

Sample Input 3

300 923223991

Sample Output 3

333532467