Problem Statement

A set A of positive integers is said to be good when it satisfies the following condition.

• For any two distinct elements a, b \in A, the string representing a in base ten is not a substring of the string representing b in base ten.

You are given positive integers L and R. Find the maximum possible number of elements in a good set A consisting of integers between L and R (inclusive).

We will give you T test cases; solve each of them.

Constraints

• 1\leq T\leq 10^4
• 1\leq L\leq R\leq 10^{9}

Sample Input 1

3
3 8
3 18
1 1000

Sample Output 1

6
10
900

For the first two cases, the following are good sets A with the maximum number of elements.

• Case 1: A=\{3,4,5,6,7,8\}.
• Case 2: A=\{3,4,6,8,9,10,11,12,15,17\}.

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of positive integers and a positive integer X. You can perform the operation below any number of times, possibly zero:

• Choose an index i (1\leq i\leq N) and a non-negative integer x such that 0\leq x\leq X. Change A_i to 2A_i+x.

Find the smallest possible value of \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} after your operations.

Constraints

• 2\leq N\leq 10^5
• 1\leq X\leq 10^9
• 1\leq A_i\leq 10^9

Sample Input 1

4 2
5 8 12 20

Sample Output 1

6

Let (i, x) denote an operation that changes A_i to 2A_i+x. An optimal sequence of operations is

• (1,0), (1,1), (2,2), (3,0)

which yields A = (21, 18, 24, 20), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 6.

Sample Input 2

4 5
24 25 26 27

Sample Output 2

0

An optimal sequence of operations is

• (1,5), (1,5), (2,5), (2,1), (3,2), (3,3), (4,0), (4,3)

which yields A = (111,111,111,111), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 0.

Sample Input 3

4 1
24 25 26 27

Sample Output 3

3

Performing no operations achieves \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 3.

Sample Input 4

10 5
39 23 3 7 16 19 40 16 33 6

Sample Output 4

13

Problem Statement

You are given a positive integer N and a sequence A = (A_0, A_1, \ldots, A_{2^N-1}) of 2^N terms, where each A_i is an integer between 0 and 2^N-1 (inclusive) and A_i\neq A_j holds if i\neq j.

You can perform the following two kinds of operations on A:

• Operation +: For every i, change A_i to (A_i + 1) \bmod 2^N.
• Operation \oplus: Choose an integer x between 0 and 2^N-1. For every i, change A_i to A_i\oplus x.

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

Your objective is to make A_i = i for every i. Determine whether it is achievable. It can be proved that, under the Constraints of this problem, one can achieve the objective with at most 10^6 operations if it is achievable at all. Print such a sequence of operations.

Constraints

• 1\leq N\leq 18
• 0\leq A_i \leq 2^N - 1
• A_i\neq A_j, if i\neq j

Sample Input 1

3
5 0 3 6 1 4 7 2

Sample Output 1

Yes
4
-1 6 -1 1

The sequence of operations above changes the sequence A as follows.

• Initially: A = (5,0,3,6,1,4,7,2)
• Operation +: A = (6,1,4,7,2,5,0,3)
• Operation \oplus (x = 6)：A = (0,7,2,1,4,3,6,5)
• Operation +: A = (1,0,3,2,5,4,7,6)
• Operation \oplus (x = 1)：A = (0,1,2,3,4,5,6,7)

Sample Input 2

3
2 5 4 3 6 1 0 7

Sample Output 2

No

No sequence of operations achieves the objective.

Sample Input 3

3
0 1 2 3 4 5 6 7

Sample Output 3

Yes
0

Performing zero operations achieves the objective. Whether an empty line is printed or not does not affect the verdict.

Problem Statement

You are given positive integers S and K. A sequence of positive integers A = (A_1, A_2, \ldots, A_N) is said to be a good sequence when satisfying the following two conditions.

• 1\leq A_1 < A_2 < \cdots < A_N \leq S - 1 holds.
• \sum_{i=1}^NA_ix_i\neq S holds for any sequence of non-negative integers (x_1, x_2, \ldots, x_N).

Let A = (A_1, A_2, \ldots, A_N) be the lexicographically smallest of the good sequences with the maximum number N of terms. Print the K-th term A_K of this sequence, or -1 if K > N.

We will give you T test cases; solve each of them.

Constraints

• 1\leq T\leq 1000
• 3\leq S\leq 10^{18}
• 1\leq K \leq S - 1

Sample Input 1

13
3 1
3 2
7 1
7 2
7 3
7 4
10 1
10 2
10 3
10 4
10 5
2022 507
1000000000000000000 999999999999999999

Sample Output 1

2
-1
2
4
6
-1
3
6
8
9
-1
1351
-1

For the cases S = 3, 7, 10, the sequence A will be as follows.

• For S=3: A = (2).
• For S=7: A = (2,4,6).
• For S=10: A = (3,6,8,9).

Problem Statement

Consider the following operations on an H\times W matrix A = (A_{i,j}) (1\leq i\leq H, 1\leq j\leq W).

• Row-sort: Sort every row in ascending order. That is, sort A_{i,1},\ldots,A_{i,W} in ascending order for every i.
• Column-sort: Sort every column in ascending order. That is, sort A_{1,j},\ldots,A_{H,j} in ascending order for every j.

You are given an H\times W matrix B = (B_{i,j}). Find the number of H\times W matrices A that satisfy both of the following conditions, modulo 998244353.

• Performing row-sort and then column-sort on A produces B.
• Performing column-sort and then row-sort on A produces B.

Constraints

• 1\leq H, W\leq 1500
• 0\leq B_{i,j}\leq 9
• B_{i,j}\leq B_{i,j+1}, for any 1\leq i\leq H and 1\leq j\leq W - 1.
• B_{i,j}\leq B_{i+1,j}, for any 1\leq j\leq W and 1\leq i\leq H - 1.
• All values in input are integers.

Sample Input 1

2 2
0 0
1 2

Sample Output 1

4

The four matrices that satisfy the conditions are:

\begin{pmatrix}0&0\\1&2\end{pmatrix}, \begin{pmatrix}0&0\\2&1\end{pmatrix}, \begin{pmatrix}1&2\\0&0\end{pmatrix}, \begin{pmatrix}2&1\\0&0\end{pmatrix}.

We can verify that \begin{pmatrix}2&1\\0&0\end{pmatrix}, for example, satisfies the conditions as follows.

• Performing row-sort and then column-sort: \begin{pmatrix}2&1\\0&0\end{pmatrix}\to \begin{pmatrix}1&2\\0&0\end{pmatrix} \to \begin{pmatrix}0&0\\1&2\end{pmatrix}.

• Performing column-sort and then row-sort:\begin{pmatrix}2&1\\0&0\end{pmatrix}\to \begin{pmatrix}0&0\\2&1\end{pmatrix} \to \begin{pmatrix}0&0\\1&2\end{pmatrix}.

Sample Input 2

3 3
0 1 3
2 4 7
5 6 8

Sample Output 2

576

\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}, for example, satisfies the conditions, which can be verified as follows.

• Performing row-sort and then column-sort: \begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}\to \begin{pmatrix}5&6&7\\0&1&3\\2&4&8\end{pmatrix} \to \begin{pmatrix}0&1&3\\2&4&7\\5&6&8\end{pmatrix}.

• Performing column-sort and then row-sort: \begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}\to \begin{pmatrix}3&0&1\\4&7&2\\5&8&6\end{pmatrix} \to \begin{pmatrix}0&1&3\\2&4&7\\5&6&8\end{pmatrix}.

Sample Input 3

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

Sample Output 3

10440

Sample Input 4

1 7
2 3 3 6 8 8 9

Sample Output 4

1260

Problem Statement

There are three indistinguishable stones at integer coordinates on a number line. Consider the following operation on these stones:

• Let A, B, C be the three stones in ascending order of coordinate (ties broken arbitrarily). Perform one of the following.
  • Move A to the symmetric position with respect to B.
  • Move C to the symmetric position with respect to B.

You are given the initial coordinates a, b, c of the three stones. Find the number, modulo 998244353, of possible combinations of coordinates of the three stones after zero or more operations.

Note that the stones are indistinguishable. More strictly speaking, count the possible multisets of coordinates of the three stones.

We will give you T test cases; solve each of them.

Constraints

• 1\leq T\leq 10^5
• -10^{18}\leq a\leq b\leq c\leq 10^{18}

Sample Input 1

6
1 3 5
-2 -2 5
0 1 3
31 41 59
-123456789 0 987654321
-1000000000000000000 0 1000000000000000000

Sample Output 1

5
2
9
70
182333351
5

For (a,b,c) = (1,3,5), the five possible combinations of the three stones after operations are:

• (1,3,5), (1,1,3), (-1,1,1), (3,5,5), (5,5,7).

The figure below may be helpful.