Problem Statement

In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?

Constraints

• 1 \leq a \lt b \leq 10
• a and b are integers.

Sample Input 1

4 5

Sample Output 1

Yes

In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.

Sample Input 2

3 5

Sample Output 2

No

In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.

Sample Input 3

1 10

Sample Output 3

Yes

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

• 1 \leq N \leq 1000
• 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

7

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

Problem Statement

Takahashi has N balls. Each ball has an integer not less than 2 written on it. He will insert them in a cylinder one by one. The integer written on the i-th ball is a_i.

The balls are made of special material. When k balls with k (k \geq 2) written on them line up in a row, all these k balls will disappear.

For each i (1 \leq i \leq N), find the number of balls after inserting the i-th ball.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

5
3 2 3 2 2

Sample Output 1

1
2
3
4
3

The content of the cylinder changes as follows.

• After inserting the 1-st ball, the cylinder contains the ball with 3.
• After inserting the 2-nd ball, the cylinder contains 3, 2 from bottom to top.
• After inserting the 3-rd ball, the cylinder contains 3, 2, 3 from bottom to top.
• After inserting the 4-th ball, the cylinder contains 3, 2, 3, 2 from bottom to top.
• After inserting the 5-th ball, the cylinder momentarily has 3, 2, 3, 2, 2 from bottom to top. The two consecutive balls with 2 disappear, and the cylinder eventually contains 3, 2, 3 from bottom to top.

Sample Input 2

10
2 3 2 3 3 3 2 3 3 2

Sample Output 2

1
2
3
4
5
3
2
3
1
0

Problem Statement

You are given a rooted tree with N vertices. The root is Vertex 1.
For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i.

For each i = 1, 2, \ldots, N, let S_i denote the set of all vertices in the subtree rooted at Vertex i. (Each vertex is in the subtree rooted at itself, that is, i \in S_i.)

Additionally, for integers l and r, let [l, r] denote the set of all integers between l and r, that is, [l, r] = \lbrace l, l+1, l+2, \ldots, r \rbrace.

Consider a sequence of N pairs of integers \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big) that satisfies the conditions below.

• 1 \leq L_i \leq R_i for every integer i such that 1 \leq i \leq N.
• The following holds for every pair of integers (i, j) such that 1 \leq i, j \leq N.
  • [L_i, R_i] \subseteq [L_j, R_j] if S_i \subseteq S_j
  • [L_i, R_i] \cap [L_j, R_j] = \emptyset if S_i \cap S_j = \emptyset

It can be shown that there is at least one sequence \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big). Among those sequences, print one that minimizes \max \lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace, the maximum integer used. (If there are multiple such sequences, you may print any of them.)

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• All values in input are integers.
• The given graph is a tree.

Sample Input 1

3
2 1
3 1

Sample Output 1

1 2
2 2
1 1

(L_1, R_1) = (1, 2), (L_2, R_2) = (2, 2), (L_3, R_3) = (1, 1) satisfies the conditions.
Indeed, we have [L_2, R_2] \subseteq [L_1, R_1], [L_3, R_3] \subseteq [L_1, R_1], [L_2, R_2] \cap [L_3, R_3] = \emptyset.
Additionally, \max \lbrace L_1, L_2, L_3, R_1, R_2, R_3 \rbrace = 2 is the minimum possible value.

Sample Input 2

5
3 4
5 4
1 2
1 4

Sample Output 2

1 3
3 3
2 2
1 2
1 1

Sample Input 3

5
4 5
3 2
5 2
3 1

Sample Output 3

1 1
1 1
1 1
1 1
1 1

Problem Statement

There are integer sequences A, B, C of length M each.

C is represented by integers x_1, \dots, x_N, y_1, \dots, y_N. The first y_1 terms of C are x_1, the subsequent y_2 terms are x_2, \ldots, the last y_N terms are x_N.

B is defined by B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).

A is defined by A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).

Find the maximum value among A_1, \dots, A_M.

You will be given T test cases to solve.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• The sum of N in a single file is at most 2 \times 10^5.
• 1 \leq M \leq 10^9
• |x_i| \leq 4 \, (1 \leq i \leq N)
• y_i \gt 0 \, (1 \leq i \leq N)
• \sum_{k = 1}^N y_k = M
• All values in input are integers.

Sample Input 1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

Sample Output 1

4
53910
2000000002000000000

In the first test case, we have:

• C = (-1, -1, 2, 2, 2, -3, -3)
• B = (-1, -2, 0, 2, 4, 1, -2)
• A = (-1, -3, -3, -1, 3, 4, 2)

Thus, the maximum value among A_1, \dots, A_M is 4.

Problem Statement

Takahashi is in the square (0, 0, 0) in an infinite three-dimensional grid.

He can teleport between squares. From the square (x, y, z), he can move to (x+1, y, z), (x-1, y, z), (x, y+1, z), (x, y-1, z), (x, y, z+1), or (x, y, z-1) in one teleport. (Note that he cannot stay in the square (x, y, z).)

Find the number of routes ending in the square (X, Y, Z) after exactly N teleports.

In other words, find the number of sequences of N+1 triples of integers \big( (x_0, y_0, z_0), (x_1, y_1, z_1), (x_2, y_2, z_2), \ldots, (x_N, y_N, z_N)\big) that satisfy all three conditions below.

• (x_0, y_0, z_0) = (0, 0, 0).
• (x_N, y_N, z_N) = (X, Y, Z).
• |x_i-x_{i-1}| + |y_i-y_{i-1}| + |z_i-z_{i-1}| = 1 for each i = 1, 2, \ldots, N.

Since the number can be enormous, print it modulo 998244353.

Constraints

• 1 \leq N \leq 10^7
• -10^7 \leq X, Y, Z \leq 10^7
• N, X, Y, and Z are integers.

Sample Input 1

3 2 0 -1

Sample Output 1

3

There are three routes ending in the square (2, 0, -1) after exactly 3 teleports:

• (0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (2, 0, 0) \rightarrow(2, 0, -1)
• (0, 0, 0) \rightarrow (1, 0, 0) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)
• (0, 0, 0) \rightarrow (0, 0, -1) \rightarrow (1, 0, -1) \rightarrow(2, 0, -1)

Sample Input 2

1 0 0 0

Sample Output 2

0

Note that exactly N teleports should be performed, and they do not allow him to stay in the same position.

Sample Input 3

314 15 92 65

Sample Output 3

106580952

Be sure to print the number modulo 998244353.

Problem Statement

You are given a string S = s_1 s_2 \ldots s_N of length N consisting of 0's and 1's.

Find the maximum integer K such that there is a sequence of K pairs of integers \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) that satisfy all three conditions below.

• 1 \leq L_i \leq R_i \leq N for each i = 1, 2, \ldots, K.
• R_i \lt L_{i+1} for i = 1, 2, \ldots, K-1.
• The string s_{L_i}s_{L_i+1} \ldots s_{R_i} is strictly lexicographically smaller than the string s_{L_{i+1}}s_{L_{i+1}+1}\ldots s_{R_{i+1}}.

Constraints

• 1 \leq N \leq 2.5 \times 10^4
• N is an integer.
• S is a string of length N consisting of 0's and 1's.

Sample Input 1

7
0101010

Sample Output 1

3

For K = 3, one sequence satisfying the conditition is (L_1, R_1) = (1, 1), (L_2, R_2) = (3, 5), (L_3, R_3) = (6, 7). Indeed, s_1 = 0 is strictly lexicographically smaller than s_3s_4s_5 = 010, and s_3s_4s_5 = 010 is strictly lexicographically smaller than s_6s_7 = 10.
For K \geq 4, there is no sequence \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) satisfying the condition.

Sample Input 2

30
000011001110101001011110001001

Sample Output 2

9