Problem Statement

There is an array A_1, \ldots, A_N, and initially A_i = i for all i. Define the following routine \mathrm{shuffle}(L, R):

• If R = L + 1, swap values of A_L and A_R and terminate.
• Otherwise, run \mathrm{shuffle}(L, R - 1) followed by \mathrm{shuffle}(L + 1, R).

Suppose we run \mathrm{shuffle}(1, N). Print the value of A_K after the routine finishes.

For each input file, solve T test cases.

Constraints

• 1 \leq T \leq 1000
• 2 \leq N \leq 10^{18}
• 1 \leq K \leq N

Sample Input 1

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

Sample Output 1

2
1
2
4
1
5
3

For N=2, we do the following and get A=(2,1).

• Run \mathrm{shuffle}(1, 2), and swap A_1 and A_2.

For N=5, we do the following and get A=(2,4,1,5,3).

• Run \mathrm{shuffle}(1, 5):
  • Run \mathrm{shuffle}(1, 4):
    • Run \mathrm{shuffle}(1, 3):
      • \vdots
    • Run \mathrm{shuffle}(2, 4):
      • \vdots
  • Run \mathrm{shuffle}(2, 5):
    • Run \mathrm{shuffle}(2, 4):
      • \vdots
    • Run \mathrm{shuffle}(3, 5):
      • \vdots

Problem Statement

There is a graph with N vertices v_1, \ldots, v_N on the left, and N + 1 vertices u_1, \ldots, u_{N + 1} on the right. Each vertex v_i (1 \leq i \leq N) is connected to each vertex u_j (1 \leq j \leq N + 1), that is, the graph contains N(N + 1) edges.

We color every edge with one of the N colors 1, \ldots, N. A coloring is suitable if for each k = 1, \ldots, N there are exactly 2k edges of color k, and those edges form a simple path.

Formally, for each k = 1, \ldots, N there should exist a sequence of distinct vertices w_0, \ldots, w_{2k} such that all of the following is true:

• For each i = 0, \ldots, 2k - 1, vertices w_i and w_{i + 1} are connected with an edge of color k,
• No other edges of color k exist.

Find any suitable coloring, or determine that it doesn't exist.

For each input file, solve T test cases.

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100

Sample Input 1

2
1
2

Sample Output 1

Yes
1 1
No

Problem Statement

There are N customers named 1,\ldots,N visiting a shop. Customer i arrives at time A_i and leaves at time B_i. The queue order is first in-first out, so A_i are increasing, and B_i are increasing. Additionally, all A_i and B_i are pairwise distinct.

At the entrance there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. How many different orders of names can there be in the end? Find the count modulo 998\,244\,353.

Constraints

• 1 \leq N \leq 5 \cdot 10^5
• 1 \leq A_i < B_i \leq 2N
• A_i < A_{i + 1} (1 \leq i \leq N - 1)
• B_i < B_{i + 1} (1 \leq i \leq N - 1)
• A_i \neq B_j (i \neq j)
• All values in the input are integers.

Sample Input 1

3
1 3
2 5
4 6

Sample Output 1

3

The possible orders are (1, 2, 3), (2, 1, 3), (1, 3, 2).

Sample Input 2

4
1 2
3 4
5 6
7 8

Sample Output 2

1

The only possible order is (1, 2, 3, 4).

Problem Statement

There are positive integers N, M, and an N \times M positive integer matrix A_{i, j}. For two (strictly) increasing positive integer sequences X = (X_1, \ldots, X_N) and Y = (Y_1, \ldots, Y_M), we define the penalty D(X, Y) as \max_{1 \leq i \leq N, 1 \leq j \leq M} |X_i Y_j - A_{i, j}|.

Find two (strictly) increasing positive integer sequences X and Y such that D(X, Y) is the smallest possible.

Constraints

• 1 \leq N, M \leq 5
• 1 \leq A_{i, j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
• All values in the input are integers.

Sample Input 1

1 1
853922530

Sample Output 1

0
31415
27182

Sample Input 2

3 3
4 4 4
4 4 4
4 4 4

Sample Output 2

5
1 2 3 
1 2 3 

Sample Input 3

3 4
4674 7356 86312 100327
8737 11831 145034 167690
47432 66105 809393 936462

Sample Output 3

357
129 216 1208 
39 55 670 775 

Problem Statement

There is a non-negative integer X initially equal to S. One can perform the following operations, in any order, any number of times:

• Add 1 to X. This has a cost of A.
• Choose i between 1 and N, and replace X with X \oplus Y_i. This has a cost of C_i. Here, \oplus denotes bitwise \mathrm{XOR}.

Find the smallest total cost to make X equal to a given non-negative integer T, or report that this is impossible.

Constraints

• 1 \leq N \leq 8
• 0 \leq S, T < 2^{40}
• 0 \leq A \leq 10^5
• 0 \leq Y_i < 2^{40} (1 \leq i \leq N)
• 0 \leq C_i \leq 10^{16} (1 \leq i \leq N)
• All values in the input are integers.

Sample Input 1

1 15 0 1
8 2

Sample Output 1

5

You can make X equal to T in the following manner:

• Choose i=1 and replace X with X \oplus 8 to get X=7. This has a cost of 2.
• Add 1 to X to get X=8. This has a cost of 1.
• Choose i=1 and replace X with X \oplus 8 to get X=0. This has a cost of 2.

Sample Input 2

3 21 10 100
30 1
12 1
13 1

Sample Output 2

3

Sample Input 3

1 2 0 1
1 1

Sample Output 3

-1

Sample Input 4

8 352217 670575 84912
239445 2866
537211 16
21812 6904
50574 8842
380870 5047
475646 8924
188204 2273
429397 4854

Sample Output 4

563645

Problem Statement

There are positive integers N and M.

A binary string s is called good if all of the followings are satisfied:

• s is non-empty.
• The number of 1s in s is a multiple of N.
• The number of 0s in s is a multiple of M.

A good string is called perfect if it doesn't contain shorter good (contiguous) substrings. For example, if N = 3 and M = 2, then strings 111, 00 and 10101 are perfect, but 0000 and 11001 are not.

One can show that for any N, M the number of perfect strings is finite. Find this number modulo 998\,244\,353.

Constraints

• 1 \leq N, M \leq 40
• All values in the input are integers.

Sample Input 1

2 2

Sample Output 1

4

The perfect strings are 00, 0101, 1010, 11.

Sample Input 2

3 2

Sample Output 2

7

The perfect strings are 00, 01011, 01101, 10101, 10110, 11010, 111.

Sample Input 3

23 35

Sample Output 3

212685109