Problem Statement

For a positive integer n, let \mathrm{str}(n) be the string representing n in decimal.

We say that a positive integer n is periodic when there exists a positive integer m such that \mathrm{str}(n) is the concatenation of two or more copies of \mathrm{str}(m). For example, 11, 1212, and 123123123 are periodic.

You are given a positive integer N at least 11. Find the greatest periodic number at most N. It can be proved that there is at least one periodic number at most N.

You will get T test cases to solve.

Constraints

• 1 \leq T \leq 10^4
• 11 \leq N < 10^{18}
• All values in input are integers.

Sample Input 1

3
1412
23
498650499498649123

Sample Output 1

1313
22
498650498650498650

For the first test case, the periodic numbers at most 1412 include 11, 222, 1212, 1313, and the greatest is 1313.

Problem Statement

You are given positive integers N and M.

Find the number of sequences A=(A_1,\ A_2,\ \dots,\ A_N) of N positive integers that satisfy the following conditions, modulo 998244353.

• 1 \leq A_1 < A_2 < \dots < A_N \leq M.
• B_1 < B_2 < \dots < B_N, where B_i = A_1 \oplus A_2 \oplus \dots \oplus A_i.

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

Constraints

• 1 \leq N \leq M < 2^{60}
• All values in input are integers.

Sample Input 1

2 4

Sample Output 1

5

For example, (A_1,\ A_2)=(1,\ 3) counts, since A_1 < A_2 and B_1 < B_2 where B_1=A_1=1,\ B_2=A_1\oplus A_2=2.

The other pairs that count are (A_1,\ A_2)=(1,\ 2),\ (1,\ 4),\ (2,\ 4),\ (3,\ 4).

Sample Input 2

4 4

Sample Output 2

0

Sample Input 3

10 123456789

Sample Output 3

205695670

Problem Statement

A string of length 2N, S=S_1S_2\dots S_{2N}, is said to be a parenthesis sequence when S is composed of N (s and N )s.

Additionally, a parenthesis sequence S is said to be correct when it is one of the following.

• An empty string.
• The concatenation of (, A, ) in this order, where A is a correct parenthesis sequence.
• The concatenation of A, B in this order, where A and B are non-empty correct parenthesis sequences.

You are given two permutations P=(P_1,\ P_2,\ \dots,\ P_{2N}) and Q=(Q_1,\ Q_2,\ \dots,\ Q_{2N}) of the integers from 1 to 2N.

Determine whether there exists a parenthesis sequence S=S_1S_2\dots S_{2N} that satisfies the following conditions.

• P is the lexicographically smallest permutation p of the integers from 1 to 2N such that S_{p_1}S_{p_2}\dots S_{p_{2N}} is a correct parenthesis sequence.
• Q is the lexicographically largest permutation p of the integers from 1 to 2N such that S_{p_1}S_{p_2}\dots S_{p_{2N}} is a correct parenthesis sequence.

If such a parenthesis sequence exists, find one.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i,Q_i \leq 2N
• Each of P and Q is a permutation of 1 to 2N.
• All values in input are integers.

Sample Input 1

2
1 2 4 3
4 3 1 2

Sample Output 1

())(

For S= ())(, some of the permutations p such that S_{p_1}S_{p_2}S_{p_3}S_{p_4} is a correct parenthesis sequence are p=(1,\ 4,\ 2,\ 3),\ (1,\ 4,\ 3,\ 2). The lexicographically smallest and largest among them are p=(1,\ 2,\ 4,\ 3) and p=(4,\ 3,\ 1,\ 2), satisfying the conditions.

Sample Input 2

2
1 3 2 4
4 3 2 1

Sample Output 2

-1

No S satisfies the conditions.

Sample Input 3

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

Sample Output 3

-1

Problem Statement

We say that a set S of positive integers is good when, for any a,\ b \in S\ (a\neq b), b is not a multiple of a.

You are given a set of N integers between 1 and 2M (inclusive): S=\lbrace A_1,\ A_2,\ \dots,\ A_N\rbrace.

For each i=1,\ 2,\ \dots,\ N, determine whether there exists a good set with M elements that is a subset of S containing A_i.

Constraints

• M \leq N \leq 2M
• 1 \leq M \leq 3 \times 10^5
• 1 \leq A_1 < A_2 < \dots < A_N \leq 2M
• All values in input are integers.

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

No
Yes
Yes
Yes
Yes

Trivially, the only good set containing A_1=1 is \lbrace 1\rbrace, which has just one element, so the answer for i=1 is No.

There is a good set \lbrace 2,\ 3,\ 5\rbrace containing A_2=2, so the answer for i=2 is Yes.

Sample Input 2

4 4
2 4 6 8

Sample Output 2

No
No
No
No

Sample Input 3

13 10
2 3 4 6 7 9 10 11 13 15 17 19 20

Sample Output 3

No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

There is an undirected graph with N^2 vertices. Initially, it has no edges. For each pair of integers (i,\ j) such that 0 \leq i,\ j < N, the graph has a corresponding vertex called (i,\ j).

You will get Q queries, which should be processed in order. The i-th query, which gives you four integers a_i,\ b_i,\ c_i,\ d_i, is as follows.

• For each k (0 \leq k < N), add an edge between two vertices ((a_i+k) \bmod N,\ (b_i+k) \bmod N) and ((c_i+k) \bmod N,\ (d_i+k) \bmod N). Then, print the current number of connected components in the graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i,\ b_i,\ c_i,\ d_i < N
• (a_i,\ b_i) \neq (c_i,\ d_i)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

6
4
4

The first query adds an edge between (0,\ 0),\ (1,\ 2), between (1,\ 1),\ (2,\ 0), and between (2,\ 2),\ (0,\ 1), changing the number of connected components from 9 to 6.

Sample Input 2

4 3
0 0 2 2
2 3 1 2
1 1 3 3

Sample Output 2

14
11
11

The graph after queries may not be simple.

Sample Input 3

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

Sample Output 3

31
27
21
21
19

Problem Statement

You are given N srings S_i\ (1\le i \le N) consisting of A, B, C, D.

Consider the operation below on a string T consisting of A, B, C, D.

• Repeat the following until T contains none of the strings S_i as a substring.
  • Choose an S_i and one of its occurrences in T, remove that occurrence from T, and concatenate the remaining parts.

We say that the string T is bad when multiple strings can result from the operation above.

Determine whether a bad string exists.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq |S_i| \leq 2 \times 10^6
• |S_1|+|S_2|+\dots +|S_N| \leq 2 \times 10^6
• S_i \neq S_j if i\neq j.
• S_i is a string consisting of A, B, C, D.

Sample Input 1

3
A
B
C

Sample Output 1

No

The only string we can get from T is what remains after removing all occurrences of A, B, C from T.

Sample Input 2

1
ABA

Sample Output 2

Yes

For example, from T= ABABA, we can get two strings: AB and BA, so T is a bad string.

Sample Input 3

4
CBA
ACB
AD
CAB

Sample Output 3

Yes