Problem Statement

You are given a graph G consisting of N vertices numbered 1, 2, \ldots, N. Initially, G has no edges.

You will add M undirected edges to G. The final shape of the graph is predetermined, and the i-th edge to be added (1 ≤ i ≤ M) connects vertices u_i and v_i. We will refer to this as edge i.
It is guaranteed that the resulting graph will be simple.

Determine if there exists a permutation (P_1, P_2, \ldots, P_M) of (1, 2, \ldots, M) that satisfies the following conditions, and if such a permutation exists, show an example.

Conditions

You must be able to add all M edges to G by following this procedure:

• For i = 1, 2, \dots, M, repeat the following:
  1. If there is already a cycle in G containing either vertex u_{P_i} or vertex v_{P_i}, the condition is not satisfied, and the procedure ends.
  2. Add edge P_i (the undirected edge connecting u_{P_i} and v_{P_i}) to G.

You are given T test cases; solve each of them.

Constraints

• All input values are integers.
• 1 \le T \le 2000
• For each test case:
  • 2 \le N \le 4000
  • 1 \le M \le 4000
  • 1 \le u_i, v_i \le N\ (1 ≤ i ≤ M)
  • The graph formed by adding all given edges is simple.
• The sum of N over all test cases is at most 4000.
• The sum of M over all test cases is at most 4000.

Subtasks

30 points will be awarded for passing the test set satisfying:

• T \le 50
• For each test case:
  • N \le 100
  • M \le 100
• The sum of N over all test cases is at most 100.
• The sum of M over all test cases is at most 100.

Sample Input 1

1
4 4
1 2
2 3
3 4
4 2

Sample Output 1

2 4 1 3

The given graph has the following shape:

If we add the edges in the order P = (1, 2, 3, 4), the conditions are satisfied as shown below:

Thus, 1 2 3 4 is one valid output.

However, if we add edges in the order P = (2, 3, 4, 1), a cycle containing vertex 2 is created before edge 1 can be added, so the conditions are not satisfied.

Other valid outputs include P = (1, 4, 3, 2) or P = (2, 4, 1, 3).

Sample Input 2

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

Sample Output 2

-1
3 2 1
4 10 2 8 7 9 6 5 3 1
-1

If no valid P exists, output -1. Note that the graph is not necessarily connected.

Problem Statement

You are given a sequence S of length N, consisting of integers 1, 2, and 3. Determine the number of sequences A consisting of integers 1 and 2 such that the sequence T obtained after performing the following procedure matches S. Output the answer modulo 998244353. It can be proven that the number of such sequences A is finite.

Start with an empty sequence T. Given a sequence A consisting of integers 1 and 2, perform the following process to obtain the sequence T:

1. Set a variable C = 0.
2. If A contains at least one 1, remove the first occurrence of 1 from A and add 1 to C.
3. If A is not empty, remove the first element x of A and add x to C.
4. Append C to the end of T.
5. If A is empty, terminate the process. Otherwise, return to step 1.

Constraints

• All input values are integers.
• 1 \le N \le 10^6
• 1 \le S_i \le 3

Sample Input 1

2
3 2

Sample Output 1

5

There are 5 possible sequences A that result in T = (3, 2): A = (1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 1, 1, 1), (1, 2, 1, 1).

For example, for A = (2, 1, 1, 1), the process proceeds as follows:

• Remove the first occurrence of 1 in A, which is A_2 = 1. Now A = (2, 1, 1) and C = 1.
• Remove the first element of A, which is A_1 = 2. Now A = (1, 1) and C = 3.
• Append C to the end of T. Now T = (3).
• Remove the first occurrence of 1 in A, which is A_1 = 1. Now A = (1) and C = 1.
• Remove the first element of A, which is A_1 = 1. Now A = () and C = 2.
• Append C to the end of T. Now T = (3, 2).

Sample Input 2

6
3 2 2 3 2 1

Sample Output 2

4

Sample Input 3

5
3 2 1 3 2

Sample Output 3

0

Note that there may be cases where no sequence A produces S, in which case the answer is 0.

Problem Statement

You are given an undirected graph G with 2^N + 1 vertices and 2^{N+1} - 1 edges. The vertices are numbered 0, 1, \dots, 2^N, and the edges are numbered 1, 2, \dots, 2^{N+1}-1.

Each edge in G belongs to one of N+1 types, ranging from type 0 to type N.
For type i (0 \le i \le N), there are exactly 2^i edges, which are numbered 2^i+0, 2^i+1, \dots, 2^i+(2^i-1). The edge numbered 2^i + j (0 \leq j \leq 2^i - 1) is an undirected edge of length C_{2^i + j} that connects vertex j \times 2^{N-i} and vertex (j+1) \times 2^{N-i}.

For example, when N = 3, G looks like the following graph:

You are given Q queries to process. There are two types of queries:

• 1 j x: Change the length of edge j to x.
• 2 s t: Find the shortest path length from vertex s to vertex t.

Constraints

• All input values are integers.
• 1 \le N \le 18
• 1 \le C_j \le 10^7 (1 \le j \le 2^{N+1}-1)
• 1 \le Q \le 2 \times 10^5
• In the query 1 j x, 1 \le j \le 2^{N+1}-1 and 1 \le x \le 10^7.
• In the query 2 s t, 0 \le s < t \le 2^N.
• There is at least one 2 s t query.

Partial Score

30 points will be awarded for passing the testset satisfying the additional constraint: There is no 1 j x query.

Sample Input 1

3
7 1 14 3 9 4 8 2 6 5 5 13 8 2 3
10
2 0 1
2 0 4
2 4 6
2 4 8
2 3 5
1 6 30
2 3 5
2 4 6
1 1 10000000
2 0 8

Sample Output 1

2
1
4
8
17
18
13
15

• In the 1st query, using edge 8, the path 0 \to 1 results in a total distance of 2.
• In the 2nd query, using edge 2, the path 0 \to 4 results in a total distance of 1.
• In the 3rd query, using edge 6, the path 4 \to 6 results in a total distance of 4.
• In the 4th query, using edges 2, 1, the path 4 \to 0 \to 8 results in a total distance of 8.
• In the 5th query, using edges 11, 6, 13, the path 3 \to 4 \to 6 \to 5 results in a total distance of 17.
• In the 6th query, the length of edge 6 is updated from 4 to 30.
• In the 7th query, using edges 11, 12, the path 3 \to 4 \to 5 results in a total distance of 18.
• In the 8th query, using edges 2, 1, 15, 14, the path 4 \to 0 \to 8 \to 7 \to 6 results in a total distance of 13.
• In the 9th query, the length of edge 1 is updated from 7 to 10000000.
• In the 10th query, using edges 2, 3, the path 0 \to 4 \to 8 results in a total distance of 15.

Problem Statement

You are given non-negative integers A, B, and C. Define a sequence of non-negative integers X = (X_1, X_2, \dots) as follows:

• X_1 = A
• X_2 = B
• X_{i+2} = (X_i \oplus X_{i+1}) + C\ \ (i=1,2,\dots)

Here, \oplus represents the bitwise XOR operation.

You are also given a positive integer N. Calculate X_N \bmod 998244353.

Constraints

• All input values are integers.
• 0 \leq A, B, C < 2^{20}
• 1 \leq N \leq 10^{18}

Sample Input 1

1 2 3 4

Sample Output 1

7

X = (1, 2, 6, 7, \dots). Here, X_4 = 7 is the answer.

Sample Input 2

123 456 789 123456789

Sample Output 2

567982455

Sample Input 3

0 0 0 1000000000000000000

Sample Output 3

0

Problem Statement

On the xy-plane, there are N points labeled 1, 2, \dots, N. The coordinates of point i (1 \le i \le N) are (X_i, Y_i).

There is a robot at the origin of this plane. Your task is to control the robot to visit all the points 1, 2, \dots, N in this order.

The robot has a string variable S, which is initially an empty string.
You can move the robot using the following four types of operations:

• Operation 1: Increase the robot's x coordinate by 1 and append X to the end of S. This operation costs 1.
• Operation 2: Increase the robot's y coordinate by 1 and append Y to the end of S. This operation costs 1.
• Operation 3: Decrease the robot's x coordinate by 1 and remove the last character of S. This operation can only be performed if the last character of S is X. This operation costs 0.
• Operation 4: Decrease the robot's y coordinate by 1 and remove the last character of S. This operation can only be performed if the last character of S is Y. This operation costs 0.

Find the minimum cost required for the robot to visit all points 1, 2, \dots, N in this order.

Constraints

• All input values are integers.
• 1 \le N \le 500
• 0 \le X_i, Y_i \le 10^9

Sample Input 1

2
3 3
1 2

Sample Output 1

6

By performing Operation 1 once, Operation 2 three times, and Operation 1 twice, you can reach point 1.
Then, by performing Operation 3 twice and Operation 4 once, you can reach point 2.

The total cost of this sequence of operations is the sum of the number of times Operations 1 and 2 are performed, which is 6.

Sample Input 2

3
2 2
3 3
1 3

Sample Output 2

7

Problem Statement

You are given N lines on the xy-plane. The i-th line (1 \le i \le N) passes through two distinct points (a_i, b_i) and (c_i, d_i). Specifically, (a_1, b_1, c_1, d_1) = (0, 0, 1, 0) and (a_2, b_2, c_2, d_2) = (0, 0, 0, 1). That is, the first line represents the x-axis, and the second line represents the y-axis.

Alice is on the xy-plane. She can perform the following operation any number of times (including zero):

Choose one of the N given lines. Alice moves to the position symmetric to her current position with respect to the chosen line.

Additionally, we define that point P is reachable from point S if the following condition is satisfied:

For any real number \varepsilon > 0, there exists a point Q such that the Euclidean distance between Q and P is at most \varepsilon, and Alice can move from S to Q in a finite number of operations.

Answer Q queries. For the i-th query (1 \le i \le Q), you are given integers X_i, Y_i, Z_i, W_i. Output Yes if (Z_i, W_i) is reachable from (X_i, Y_i). Otherwise, output No.

Solve the problem for T test cases.

Constraints

• All input values are integers.
• 1 \le T \le 100
• For each test case:
  • 2 \le N \le 2000
  • 1 \le Q \le 2000
  • -10^8 \le a_i, b_i, c_i, d_i \le 10^8 \ (1 \le i \le N)
  • (a_i, b_i) \neq (c_i, d_i)
  • (a_1, b_1, c_1, d_1) = (0, 0, 1, 0)
  • (a_2, b_2, c_2, d_2) = (0, 0, 0, 1)
  • All given lines are distinct.
  • -10^8 \le X_i, Y_i, Z_i, W_i \le 10^8 \ (1 \le i \le Q)

Sample Input 1

2
3
0 0 1 0
0 0 0 1
0 2 2 0
4
1 0 2 3
1 -2 -1 2
1 1 -1 0
3 3 3 3
3
0 0 1 0
0 0 0 1
-2 1 2 3
2
2 1 -1 5
-1 -1 3 3

Sample Output 1

Yes
Yes
No
Yes
Yes
Yes

Let us explain the first test case. For the first query, Alice can use the second and third lines in sequence to move (1, 0) \to (-1, 0) \to (2, 3). Thus, (2, 3) is reachable from (1, 0). Note that for the fourth query, if (X_i, Y_i) = (Z_i, W_i), the destination is always reachable.

Now let us explain the second test case. For the first query, Alice can use the first and third lines in sequence to move (2, 1) \to (2, -1) \to \left(-\frac{6}{5}, \frac{27}{5}\right). The distance between (-1, 5) and \left(-\frac{6}{5}, \frac{27}{5}\right) is \frac{1}{\sqrt{5}}. This means that for \varepsilon \ge \frac{1}{\sqrt{5}}, Alice can find a point Q that satisfies the "reachable" condition. Moreover, for any \varepsilon > 0, Alice can find such a point Q. As a result, (2, 1) is reachable from (-1, 5).

Problem Statement

You are given a tree A with N vertices. The vertices of A are numbered 1, 2, \dots, N, and the i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i of A.

Additionally, you are given another tree B with N vertices. The vertices of B are also numbered 1, 2, \dots, N, and the j-th edge (1 \leq j \leq N-1) connects vertices x_j and y_j of B.

Your task is to find a pair of permutations ((P_1, P_2, \dots, P_{N-1}), (Q_1, Q_2, \dots, Q_{N-1})) that satisfies the following conditions:

Conditions

Perform the following operations 1. and 2. in order for k = 1, 2, \dots, N-1. After completing operations 1. and 2. for each k, both A and B must remain as trees.

1. In tree A, remove the edge connecting vertices u_{P_k} and v_{P_k}, and add an edge connecting vertices x_{Q_k} and y_{Q_k}.
2. In tree B, remove the edge connecting vertices x_{Q_k} and y_{Q_k}, and add an edge connecting vertices u_{P_k} and v_{P_k}.

It can be proven that under the constraints of this problem, a valid solution always exists.

Constraints

• All input values are integers.
• 2 \leq N \leq 1000
• 1 \leq u_i, v_i, x_j, y_j \leq N
• The given A and B form trees.

Sample Input 1

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

Sample Output 1

3 1 2
2 1 3

Before the operation, A is a path graph, and B is a star graph.

After the operation for k = 1, A becomes a star graph, and B becomes a path graph.

In the operations for k = 2, the same edge (in terms of vertex numbers) is removed and added, so the shape of the tree remains unchanged.

After completing the operations for k = 3, the original shapes of trees A and B are completely swapped.

Sample Input 2

2
1 2
2 1

Sample Output 2

1
1

Sample Input 3

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

Sample Output 3

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

Problem Statement

A set of points U in the xy-plane is called good if no point in U lies in the interior of the convex hull of U. Note that the empty set is considered good.

You are given N distinct points v_1, v_2, \dots, v_N in the xy-plane. The coordinates of the point v_i are (x_i, y_i). No three distinct points are collinear.

Count the number of subsets S of V = \lbrace v_1, v_2, \dots, v_N \rbrace such that both S and V \setminus S are good sets.

Constraints

• All input values are integers.
• 1 \le N \le 40
• |x_i|,|y_i|\le 10^6
• (x_i,y_i)\neq (x_j,y_j)\ (i\neq j)
• No three distinct points are collinear.

Sample Input 1

4
0 0
3 0
0 3
1 1

Sample Output 1

14

Except for \emptyset and V, all other sets S satisfy the condition.

Sample Input 2

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

Sample Output 2

256

Sample Input 3

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

Sample Output 3

0

Problem Statement

This is an interactive problem, where your program interacts with the judge system via Standard Input and Output.

You are given integers N, K, and Q.
The judge holds a hidden permutation (a_1, a_2, \dots, a_N) of (1, 2, \dots, N).
You may ask up to Q queries to the judge, where each query is as follows:

• Choose a subset S from \lbrace 1, 2, \dots, N \rbrace. The judge will return the number of distinct pairs (i, j) such that i < j and |a_i - a_j| \leq K where i, j \in S.

Let x be the index t where a_t = 1, and y be the index t where a_t = N. Your task is to identify the set \lbrace x, y \rbrace. (You do not need to distinguish which is x and which is y.)

The judge is non-adaptive, that means the permutation (a_1, a_2, \dots, a_N) is fixed before any interaction begins.

Constraints

• All input values are integers.
• N = 20000
• 1 \leq K \leq 10
• Q = 30(K + 1)

Partial Score

30 points will be awarded for passing the test set satisfying the additional constraint K = 10.

Problem Statement

You are given positive integers H and W. You aim to draw an H-row by W-column grid on the coordinate plane using several "U-shapes."

To draw one U-shape, perform the following operation:

• Choose integers 1 \le x \le H and 1 \le y \le W.
• From the following four line segments, select any three distinct ones:
  • The line segment connecting (x-1, y-1) and (x-1, y)
  • The line segment connecting (x-1, y-1) and (x, y-1)
  • The line segment connecting (x, y) and (x-1, y)
  • The line segment connecting (x, y) and (x, y-1)
• Draw the selected three line segments on the coordinate plane.

However, the line segments you draw must not share any points (other than endpoints) with any line segments drawn previously.

Is it possible to draw all the length-1 line segments connecting grid points with 0 \le x \le H and 0 \le y \le W by repeating this operation? If possible, provide an example.

Constraints

• All input values are integers.
• 1 \le H, W \le 1000

Partial Score

10 points will be awarded for passing the testset satisfying the additional constraint H,W\le 5.

Sample Input 1

3 3

Sample Output 1

Yes
<<^
v.^
v>>

As shown in the figure, you can draw a 3 \times 3 grid by drawing U-shapes. Note that no U-shape is drawn at the location corresponding to the center cell. (For clarity, the U-shapes are colored, but this is irrelevant to the problem.)

Sample Input 2

4 4

Sample Output 2

No

Sample Input 3

4 5

Sample Output 3

No

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N consisting of 0s and 1s. Define a simple undirected graph G = (V, E) with \frac{N (N - 1)}{2} vertices as follows:

• For every pair of integers (i, j) satisfying 1 \leq i < j \leq N, (i, j) \in V. This vertex is called vertex (i, j).
• For every triple of integers (i, j, k) satisfying 1 \leq i < j < k \leq N and A_i + A_j + A_k = 1, there is an edge connecting vertex (i, j) and vertex (j, k).
• No other pairs of vertices have edges.

Determine the number of connected components in G.

You are given T test cases. For each test case, compute the answer.

Constraints

• All input values are integers.
• 1 \leq T \leq 10^5
• 3 \leq N \leq 10^6
• A_i is 0 or 1 (1 \leq i \leq N)
• The total sum of N over all test cases in a single input is at most 10^6.

Partial Score

30 points will be awarded for passing the test set satisfying the following constraints:

• 1 \leq T \leq 1000
• 3 \leq N \leq 5000
• The total sum of N over all test cases in a single input is at most 5000.

Sample Input 1

4
5
1 0 0 1 0
5
1 1 1 1 1
12
0 0 1 1 1 0 0 0 1 0 1 0
20
0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 1

Sample Output 1

4
10
13
58

For the first test case, the connected components are as follows:

• \lbrace (1,2),(2,3),(2,4),(2,5),(3,4),(4,5) \rbrace
• \lbrace (1,3),(3,5) \rbrace
• \lbrace (1,4) \rbrace
• \lbrace (1,5) \rbrace

For the second test case, the graph has no edges, so the number of connected components is 10.

Problem Statement

In this problem, when we refer to a "permutation of length K", we mean a permutation of (0, 1, \dots, K - 1). Also, we denote the k-th element (0-based) of a sequence X as X[k].

You are given a permutation P of length L, and L permutations of length B, denoted as V_{0}, V_{1}, \dots, V_{L - 1}.
We define a sequence A of length B^L as follows:

For each 0 ≤ n < B^L, when n is represented as an L-digit number in base B, let N[i] be the value at the B^i place (0 ≤ i < L). Then,

\displaystyle A[n] = \sum_{i=0}^{L-1} V_i[N[i]] \cdot B^{P[i]}

Find the inversion number of the sequence A modulo 998244353.

Constraints

• All input values are integers
• 1 \leq L
• 2 \leq B
• L \times (B + 1) \leq 5 \times 10^{5}
• P is a permutation of length L
• For each 0 \leq i < L, V_{i} is a permutation of length B

Sample Input 1

3 2
2 0 1
1 0
1 0
0 1

Sample Output 1

14

For example, when n = 5, since N = (1, 0, 1), we have A[5] = V_{0}[1] \cdot 2^{P[0]} + V_{1}[0] \cdot 2^{P[1]} + V_{2}[1] \cdot 2^{P[2]}=3.
By calculating similarly, we get A = (5, 1, 4, 0, 7, 3, 6, 2). The inversion count of A is 14, so output 14.

Sample Input 2

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

Sample Output 2

60

A = (9, 1, 13, 5, 10, 2, 14, 6, 11, 3, 15, 7, 8, 0, 12, 4). The inversion count of A is 60, so output 60.

Sample Input 3

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

Sample Output 3

138876070

Output the answer modulo 998244353.

Problem Statement

You are given a permutation A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).

For a pair of integers l, r (1 \le l \le r \le N), we define the Cartesian Tree \text{C}(l, r) as follows:

• \text{C}(l, r) is a rooted binary tree with r - l + 1 nodes. We denote the root of this tree as \mathit{rt}.
• Let m be the unique integer such that A_m = \min\lbrace A_l, A_{l+1}, \dots, A_r\rbrace.
• If l < m, then the left subtree of \mathit{rt} is \text{C}(l, m-1). If l = m, then \mathit{rt} has no left child.
• If m < r, then the right subtree of \mathit{rt} is \text{C}(m+1, r). If m = r, then \mathit{rt} has no right child.

You are given Q pairs of integers (l_1, r_1), (l_2, r_2), \dots, (l_Q, r_Q). Determine how many different Cartesian Trees are there among \text{C}(l_1, r_1), \text{C}(l_2, r_2), \dots, \text{C}(l_Q, r_Q).

Two Cartesian Trees X and Y are considered the same if and only if all of the following conditions are satisfied:

Let the root of X be \mathit{rt}_X, and the root of Y be \mathit{rt}_Y.

• If \mathit{rt}_X has a left child, then \mathit{rt}_Y also has a left child and the left subtrees of \mathit{rt}_X and \mathit{rt}_Y are the same Cartesian Tree.
• If \mathit{rt}_X has no left child, then \mathit{rt}_Y also has no left child.
• If \mathit{rt}_X has a right child, then \mathit{rt}_Y also has a right child and the right subtrees of \mathit{rt}_X and \mathit{rt}_Y are the same Cartesian Tree.
• If \mathit{rt}_X has no right child, then \mathit{rt}_Y also has no right child.

Constraints

• All input values are integers.
• 1 \le N \le 4 \times 10^5
• A is a permutation of (1, 2, \dots, N).
• 1 \le Q \le 4 \times 10^5
• 1 \le l_i \le r_i \le N (1 \le i \le Q)
• (l_i, r_i) \ne (l_j, r_j) (1 \le i < j \le Q)

Sample Input 1

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

Sample Output 1

2

\text{C}(1, 4), \text{C}(2, 5), \text{C}(3, 6) are the following Cartesian Trees:

\text{C}(1, 4) and \text{C}(3, 6) are the same Cartesian Tree, while \text{C}(2, 5) is a different Cartesian Tree from these. Therefore, there are 2 different Cartesian Trees.

Sample Input 2

4
1 2 3 4
10
1 1
2 2
3 3
4 4
1 2
2 3
3 4
1 3
2 4
1 4

Sample Output 2

4

Sample Input 3

10
3 8 4 7 2 5 9 10 1 6
13
5 8
2 6
7 9
3 8
3 5
2 4
4 6
1 9
3 7
6 9
2 10
4 9
3 9

Sample Output 3

11