Problem Statement

You are given positive integers N and M. For each j = 1, 2, \ldots, M, you are given a pair of integers (L_j, R_j) satisfying 1\leq L_j\leq R_j\leq N.

Consider a length-N positive integer sequence A = (A_1, A_2, \ldots, A_N) satisfying the following condition for all j = 1, 2, \ldots, M:

• A_{L_j}, A_{L_j+1}, \ldots, A_{R_j} are all distinct.

It can be proved that such a positive integer sequence A always exists. Among all positive integer sequences A satisfying the condition, output one that minimizes the value of \max(A_1, A_2, \ldots, A_N).

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 10^5
• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq L_j \leq R_j\leq N (1\leq j\leq M)
• All input values are integers.
• The sum of N over all test cases is at most 2\times 10^5.
• The sum of M over all test cases is at most 2\times 10^5.

Sample Input 1

2
5 1
1 5
5 3
1 2
2 3
3 5

Sample Output 1

1 2 3 4 5
3 1 2 1 3

For the first test case, the output can be verified to satisfy the condition as follows:

• A_1, A_2, A_3, A_4, A_5 are 1, 2, 3, 4, 5, which are all distinct.

In this case, \max(A_1, A_2, \ldots, A_N) = 5, which is the minimum value for a positive integer sequence satisfying the condition.

For the second test case, the output can be verified to satisfy the condition as follows:

• A_1, A_2 are 3, 1, which are all distinct.
• A_2, A_3 are 1, 2, which are all distinct.
• A_3, A_4, A_5 are 2, 1, 3, which are all distinct.

In this case, \max(A_1, A_2, \ldots, A_N) = 3, which is the minimum value for a positive integer sequence satisfying the condition.

Problem Statement

A rock-paper-scissors tournament was held with a+b+c participants. Here, a, b, c are non-negative integers with 3\leq a+b+c.

In the tournament, all participants first stand in a circle. Then, each participant plays "Rock," "Scissors," or "Paper."

For each participant, if the hand they played beats both the hand of the participant to their left and the hand of the participant to their right, that participant becomes a winner. There is not necessarily exactly one winner; there may be zero, or two or more winners.

More formally, a participant becomes a winner if one of the following holds:

• The participant played "Rock," and both the left neighbor and the right neighbor played "Scissors."
• The participant played "Scissors," and both the left neighbor and the right neighbor played "Paper."
• The participant played "Paper," and both the left neighbor and the right neighbor played "Rock."

The following is known about this tournament:

• a participants played "Rock."
• b participants played "Scissors."
• c participants played "Paper."

Under this condition, find the maximum possible number of winners in the tournament.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 5\times 10^5
• 0\leq a, b, c\leq 10^9
• 3\leq a+b+c
• All input values are integers.

Sample Input 1

6
3 1 2
2 2 2
123 456 789
10 0 0
10 0 100
100 0 10

Sample Output 1

2
1
578
0
9
10

Let us explain the first test case. Consider the case where the hands played by the six participants are represented as in the following figure. In the figure, a participant who played "Rock" is denoted by A, a participant who played "Scissors" is denoted by B, and a participant who played "Paper" is denoted by C.

In this figure, there are three participants who played "Rock," one participant who played "Scissors," and two participants who played "Paper," which matches the input. In this case, the winners of the tournament are the two participants who played "Paper."

Problem Statement

There is an N\times N grid, where N is an integer at least 2. For 1\leq i,j\leq N, the cell at row i from the top and column j from the left is denoted by (i,j).

Initially, all cells are black. For each cell (i,j), a cost A_{i,j} to change the color of the cell from black to white is given.

Alice and Bob play a game using this grid and one piece. The game consists of the following three steps.

Step 1

The referee specifies the cell where the piece is initially placed.

Step 2

Alice performs the following operation zero or more times:

• Choose a black cell (i,j), pay cost A_{i,j}, and change that cell to white.

Step 3

Place the piece on the cell specified as the initial position in Step 1. Then, starting with Alice, Alice and Bob take turns making moves.

• On Alice's turn, Alice moves the piece to an adjacent cell to the left or right.
• On Bob's turn, Bob moves the piece to an adjacent cell in any of the up, down, left, or right directions.

A move that would take the piece outside the grid is not allowed.

Step 3 ends immediately after Alice and Bob have each taken 10^{10} turns.

At the end of Step 3, if the piece is on a white cell, Alice wins; if it is on a black cell, Bob wins. In Step 3, Alice and Bob each act optimally to win.

For each cell (h,w), find the minimum total cost that Alice must pay in Step 2 to guarantee a win if (h,w) is specified as the initial cell in Step 1.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 10^4
• 2\leq N\leq 500
• 0\leq A_{i,j}\leq 10^9
• All input values are integers.
• The sum of N^2 over all test cases is at most 500^2.

Sample Input 1

3
2
1 4
3 2
3
1 2 3
8 9 4
7 6 5
4
0 0 1 0
1 0 1 1
1 1 1 0
0 1 1 1

Sample Output 1

3 7
7 3
25 20 25
20 25 20
25 20 25
4 3 4 3
4 4 3 5
4 3 4 3
3 4 3 5

Let us explain the first test case.

For (h,w) = (1,1) or (h,w) = (2,2), Alice changes cells (1,1) and (2,2) to white.

In this case, at the end of each of Bob's turns, the piece is at (1,1) or (2,2). Therefore, immediately after Alice and Bob have each taken 10^{10} turns, the piece is at (1,1) or (2,2), so Alice wins regardless of how the piece is moved. The cost Alice pays in Step 2 is A_{1,1}+A_{2,2}=1+2=3.

For (h,w) = (1,2) or (h,w) = (2,1), it can be verified that Alice can win by changing cells (1,2) and (2,1) to white. In this case, the cost Alice pays in Step 2 is A_{1,2}+A_{2,1}=4+3=7.

Problem Statement

Define the digit sum of a non-negative integer n as the sum of the digits when n is written in decimal notation. For example, the digit sum of 2026 is 2+0+2+6=10.

You are given positive integer sequences A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

Using A and B, define an integer sequence X=(X_0,X_1,X_2,\ldots,X_N) as follows:

• Set X_0 = 0.
• For each i=1,2,\ldots,N, choose one of X_i = 10X_{i-1} + A_i and X_i = 10X_{i-1} + B_i to determine X_i.

For each k=1,2,\ldots,N, find the minimum possible digit sum of X_k.

Solve independently for each k. That is, for different k, the way to determine the integer sequence X that minimizes the digit sum of X_k may be different.

Constraints

• 1\leq N\leq 20000
• 1\leq A_i \leq 10^9-1
• 1\leq B_i \leq 10^9-1
• All input values are integers.

Sample Input 1

2
123 444
456 222

Sample Output 1

6 9

The possible integer sequences X=(X_0,X_1,X_2) are the following four:

• X = (0, 123, 1674)
• X = (0, 123, 1452)
• X = (0, 456, 5004)
• X = (0, 456, 4782)

The minimum possible digit sum of X_1 is 6, which is the digit sum of 123.

The minimum possible digit sum of X_2 is 9, which is the digit sum of 5004.

Sample Input 2

15
47640 28384 12457 87254 35032 27915 72870 32688 59091 95771 44037 44252 82222 87110 45829
41522 28795 85247 87801 45150 79509 15308 17923 75921 14992 71984 7601 42312 98436 36545

Sample Output 2

14 18 26 19 28 33 28 34 29 27 29 39 35 43 41

Problem Statement

There are N cards. The i-th card (1\leq i\leq N) has the integer A_i written on it. Here, 0\leq A_i \leq 2^M-1 holds.

For each integer X=0,1,\ldots,2^M-1, let f(X) denote the answer to the following problem:

Consider forming some pairs of cards.

Each pair consists of two distinct cards, and the bitwise XOR of the integers written on those two cards must equal X. The same card cannot be included in multiple pairs.

Find the maximum number of pairs that can be formed under these conditions.

Output the following value:

\[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq M\leq 20
• 0\leq A_i \leq 2^M-1 (1\leq i\leq N)
• All input values are integers.

Sample Input 1

4 2
1 1 3 3

Sample Output 1

202

• For X=0: two pairs (A_1,A_2) and (A_3,A_4) can be formed.
• For X=1: zero pairs can be formed.
• For X=2: two pairs (A_1,A_4) and (A_2,A_3) can be formed.
• For X=3: zero pairs can be formed.

Therefore, f(0)=2, f(1)=0, f(2)=2, and f(3)=0. The value to be output is 2\times 1 + 0\times 10 + 2\times 100 + 0\times 1000 = 202.

Sample Input 2

10 3
5 2 1 4 5 5 5 0 1 7

Sample Output 2

22332223

Sample Input 3

10 4
11 6 3 8 6 7 14 10 10 11

Sample Output 3

613668597

Problem Statement

Consider an operation on a triple (x,y,z) of non-negative integers. In the operation, (x,y,z) is replaced according to the following rules:

• If y+z<x: replace with (x-y-z,\ 2y,\ 2z).
• If x+z<y: replace with (2x,\ y-x-z,\ 2z).
• If x+y<z: replace with (2x,\ 2y,\ z-x-y).
• If none of the above conditions hold: replace with (y+z-x,\ x+z-y,\ x+y-z).

Note that every triple of non-negative integers falls into exactly one of the above four cases.

You are given non-negative integers A_1, A_2, A_3, B_1, B_2, B_3. Consider performing the operation on the triple (A_1,A_2,A_3) zero or more times to obtain (B_1,B_2,B_3). Find the minimum number of operations required to do so. If it is impossible to obtain (B_1,B_2,B_3) no matter how many times the operation is performed, output -1.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 300
• 0\leq A_1, A_2, A_3, B_1, B_2, B_3\leq 10^8
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
2
-1
-1
0

For (A_1,A_2,A_3)=(2,3,4), the triple changes as follows when the operation is repeatedly applied:

• (2,3,4)\to (5,3,1)\to (1,6,2)\to (2,3,4)\to (5,3,1)\to (1,6,2)\to\cdots

From this, we can see that the answers to the first three test cases are 0, 1, 2.