Problem Statement

You are given a positive integer N. A set S of positive integers between 1 and N (inclusive) is called a good set if it satisfies the following condition:

• For every pair of elements x and y in S, the remainder when x is divided by y is not 1.

Construct one good set with the maximum possible number of elements.

Constraints

• 1 \le N \le 2 \times 10^{5}

Sample Input 1

5

Sample Output 1

2
3 5

For example, \lbrace 3,5 \rbrace and \lbrace 2 \rbrace are good sets. On the other hand, \lbrace 2,3,5 \rbrace and \lbrace 1,2,3,4,5 \rbrace are not good sets.

No good set with three or more elements exists, so \lbrace 3,5 \rbrace is one of the good sets with the maximum number of elements.

Sample Input 2

2

Sample Output 2

1
2 

Problem Statement

Determine whether there exists a sequence A=(A_1,A_2,\dots,A_{X+Y+Z}) of length X+Y+Z that contains exactly X zeros, Y ones, and Z twos, and satisfies the following condition:

• For every i(1 \le i \le X+Y+Z), exactly A_i numbers among A_{i-1} and A_{i+1} are less than A_i.

Here, assume A_0 = A_{X+Y+Z} and A_{X+Y+Z+1} = A_1.

You are given T test cases. Solve each of them.

Constraints

• 1 \le T \le 2 \times 10^{5}
• 0 \le X,Y,Z \le 10^{9}
• 3 \le X + Y + Z

Sample Input 1

4
2 1 1
3 4 5
1359 1998 1022
392848293 683919483 822948689

Sample Output 1

Yes
No
Yes
No

For the first test case, the sequence A = (2,0,0,1) satisfies the condition.

For the second test case, no sequence satisfies the condition.

Problem Statement

You are given two integer sequences of length N: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

You may perform at most 31000 operations of the following kind:

• Choose a pair of integers (i,j) with 1 \le i < j \le N, then replace A_i with A_j - 1 and A_j with A_i + 1.

Your goal is to make A = B. Determine whether the goal is achievable, and if it is, output one sequence of operations that achieves it.

Constraints

• 2 \le N \le 100
• 1 \le A_i,B_i \le 100

Sample Input 1

4
2 2 1 4
3 2 2 2

Sample Output 1

Yes
2
1 4
3 4

The following operations make A = B:

• Choose (i,j) = (1,4). Then A = (3,2,1,3).
• Choose (i,j) = (3,4). Then A = (3,2,2,2).

Since minimizing the number of operations is not required, the following output is also accepted:

Yes
6
1 4
3 4
1 2
1 2
1 2
1 2

Sample Input 2

6
5 4 4 3 4 2
5 1 2 3 4 1

Sample Output 2

No

Sample Input 3

7
2 4 2 4 3 2 5
5 4 3 2 5 1 2

Sample Output 3

Yes
18
5 7
1 7
2 4
1 5
1 5
1 4
4 5
4 5
3 4
5 7
1 5
1 7
1 6
6 7
1 7
2 4
2 5
4 5

Problem Statement

You are given a tree T with N vertices numbered 1 through N, and an N \times N matrix A = (A_{i,j}). The i-th edge of T connects vertices U_i and V_i. Each entry of A is 0 or 1.

Define the score of an integer sequence x=(x_1,x_2,\dots,x_N) as follows:

• For a vertex pair (i,j)(1 \le i,j \le N), let the simple path in T from i to j be v_1=i,v_2,\dots,v_n=j (this path is unique since T is a tree). The pair (i,j) is called a palindromic pair if x_{v_k} = x_{v_{n+1-k}} for every k(1 \le k \le n).
• If there exists a pair (i,j) such that A_{i,j} = 1 and (i,j) is not a palindromic pair, then the score of x is 10^{100}.
• Otherwise, the score of x is the number of pairs (i,j) such that 1 \le i,j \le N and (i,j) is a palindromic pair.

Find the minimum score over all integer sequences x.

Constraints

• 1 \le N \le 3000
• 1 \le U_i,V_i \le N
• T is a tree.
• A_{i,j} \in \lbrace 0,1 \rbrace
• A_{i,i} = 1
• A_{i,j} = A_{j,i}

Sample Input 1

4
1 2
1 3
1 4
1000
0101
0010
0101

Sample Output 1

6

For example, when x = (1,2,4,2), there is no pair (i,j) such that A_{i,j}=1 and (i,j) is not a palindromic pair. The palindromic pairs are (1,1),(2,2),(3,3),(4,4),(2,4),(4,2), so the score is 6.

On the other hand, when x = (1,2,3,4), we have A_{2,4} = 1 while (2,4) is not a palindromic pair, so the score is 10^{100}.

Sample Input 2

7
7 2
4 1
6 5
1 6
3 4
2 3
1001000
0100000
0010000
1001001
0000100
0000010
0001001

Sample Output 2

13

Sample Input 3

10
7 5
10 3
7 6
6 10
8 3
9 3
5 4
1 5
2 10
1000000000
0100010000
0010010100
0001000000
0000100100
0110010000
0000001001
0010100110
0000000110
0000001001

Sample Output 3

66

Problem Statement

You are given a set S = \lbrace s_1,s_2,\dots,s_M \rbrace of non-negative integers between 0 and 2^N - 1 (inclusive).

You start with a non-negative integer x = 0. Find the number, modulo 998244353, of ways to reach x = 2^N by performing the following operation any number of times:

• Choose an integer i with 1 \le i \le M, and replace x with (x\ \mathrm{OR}\ s_i) + 1.

Here, \mathrm{OR} denotes the bitwise logical OR.

Constraints

• 1 \le N \le 24
• 1 \le M \le \min(2^N,2 \times 10^{5})
• 0 \le s_1 < s_2 < \dots < s_M < 2^N

Sample Input 1

2 2
1 2

Sample Output 1

5

Let (i, k) denote the transition when an operation chooses i and results in x = k. There are five ways that satisfy the conditions:

• (1,2) \rightarrow (1,4)
• (1,2) \rightarrow (2,3) \rightarrow (1,4)
• (1,2) \rightarrow (2,3) \rightarrow (2,4)
• (2,3) \rightarrow (1,4)
• (2,3) \rightarrow (2,4)

Even if the sequence of values of x is identical, ways that differ in the choices of i are counted separately.

Sample Input 2

5 10
3 5 8 9 11 16 17 23 27 28

Sample Output 2

242816764

Sample Input 3

24 32
673802 709603 941436 987977 1288854 1448514 1890649 2031791 2194398 3531579 3540682 4352378 4676427 5094869 5243789 6064976 6412917 7164733 8403938 9123034 10396333 10558625 10726446 12263566 12421464 12503511 12676340 14032527 14268967 14669703 15823827 16285412

Sample Output 3

508425421