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 two sequences of non-negative integers A and B, each of length N. Initially, A=(A_1, A_2, \ldots, A_N) and B=(B_1, B_2, \ldots, B_N).

You will be given Q queries. Process them in the order they are given.

Each query is one of the following two types:

• Type 1: Given in the format 1 i a b. Update the value of A_i to a and the value of B_i to b.
• Type 2: Given in the format 2 Y 0 0. Solve the following problem:

  For a non-negative integer S, define a sequence of non-negative integers X = (X_0, X_1, \dots, X_N) using the following recurrence:

  • X_0 = S
  • For each 1 \le i \le N, X_i = \begin{cases} X_{i - 1} \oplus A_i & \text{if } X_{i - 1} \equiv 1 \pmod{2} \\ X_{i - 1} \oplus B_i & \text{if } X_{i - 1} \equiv 0 \pmod{2} \end{cases}

  Determine whether it is possible to set a non-negative integer S such that X_N = Y. If possible, output the smallest such S.
  If no such S exists, output -1.

Constraints

• All inputs are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 0 \le A_i, B_i < 2^{60} \ (1 \le i \le N)
• For a Type 1 query, 1 \le i \le N, 0 \le a, b < 2^{60}
• For a Type 2 query, 0 \le Y < 2^{60}
• There is at least one Type 2 query.

Partial Score

30 points will be awarded for passing the test set satisfying the additional constraint Q=1.

Sample Input 1

1 3
0
1
2 5 0 0
2 6 0 0
2 7 0 0

Sample Output 1

4
-1
6

Given A = (0),\ B = (1), the value of X_N is:

• X_N = S if S is odd.
• X_N = S \oplus 1 if S is even.

For the first query with Y = 5, both S = 4 and S = 5 result in X_N = 5, so the smallest S is 4.
For the second query with Y = 6, there is no S such that X_N = 6, so output -1.
For the third query with Y = 7, both S = 6 and S = 7 result in X_N = 7, so the smallest S is 6.

Sample Input 2

10 1
310214852498133736 505276263682091678 273987911350501637 317207700241861186 878845869214220663 722059890180131902 597424946894933345 74297940232615233 969543184238991085 567669635596262039
760374976835769237 114205047640377864 975115657391620675 659404150340533368 514313531921108960 255579815636209538 1042405225853490071 891193105039531117 1032475514675208675 968262176137127595
2 942999108116930288 0 0

Sample Output 2

494185924924343867

Sample Input 3

10 5
20 19 18 17 16 15 14 13 12 11
11 12 13 14 15 16 17 18 19 20
2 8 0 0
1 6 100 200
2 12 0 0
1 10 32 662
2 100 0 0

Sample Output 3

8
103
-1

Sample Input 4

10 5
464468010685205695 652469322679259637 207750579744900414 551282264132274959 477385551779769369 457669217633528368 1124978699497706079 993018743713584412 347799342391956023 253839229959865684
43481420251962425 913779804742334221 721829783836314668 643562100144275666 148532568860178532 348780722732705987 905040003050597634 962374691997649953 160408954061784257 6313574278114070
2 942999108116930288 0 0
1 7 911289147093700219 315969390490734880
2 570806468566359262 0 0
1 5 865153057674787555 127079554510737035
2 71991180131886804 0 0

Sample Output 4

167766290121628811
833427363106128513
657636533261400102

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 a string S, T of length N consisting of only uppercase English letters. You can perform the following operation 0 or more times:

• If there exists a substring of S such that TIOT, choose one and replace it with ISCT. (More precisely, if there exists 1 \le i \le N-3 such that S_{i}={}T, S_{i+1}={}I, S_{i+2}={}O, S_{i+3}={}T, choose one and replace it with S_{i}={}I, S_{i+1}={}S, S_{i+2}={}C, S_{i+3}={}T.)

Can you make S equal to T by performing the operation?

You have Q test cases to answer.

Constraints

• 1 \leq Q \leq 5 \times 10^4
• 4 \le N \le 2 \times 10^5
• S and T are strings of length N consisting of uppercase English letters.
• The sum of N across the test cases is at most 2 \times 10^5.

Sample Input 1

3
10
ETIOTROPIC
EISCTROPIC
6
BTIEOT
BISECT
10
TIOTIOTIOT
TIOISCISCT

Sample Output 1

Yes
No
Yes

For the first test case, you can match ETIOTROPIC to EISCTROPIC by performing the operation once as follows:

• The substring from the 2 nd to 5 th characters in ETIOTROPIC is TIOT, so replace it with ISCT.

For the second test case, you cannot match two strings through the operation.

Problem Statement

You are given a rooted tree with N vertices. The vertices are numbered from 1 to N, with vertex 1 being the root. The i-th edge connects vertex A_i and vertex B_i.

Assign a color to each vertex such that the following condition is satisfied:

• Let the color of vertex i be c_i. For any three distinct vertices u, v, and w, if w = \mathrm{lca}(u, v) and c_u = c_v, then c_u \neq c_w.

Find the minimum possible number of distinct colors used.

Here, \mathrm{lca}(u, v) denotes the lowest common ancestor of vertices u and v.

Constraints

• All input values are integers.
• 3 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The input graph is a tree.

Sample Input 1

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

Sample Output 1

3

For example, the coloring shown below satisfies the given conditions.

Since there is no way to satisfy the conditions using two or fewer colors, the minimum number of colors needed is 3.

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

1

Problem Statement

The abbreviation-deciding machine \mathrm{M} for a programming contest has a string S of length N consisting of uppercase English letters and an integer sequence A = (A_1, A_2, \dots, A_N) of length N.
Additionally, machine \mathrm{M} has four cursors numbered from 1 to 4 for pointing at characters in S. Initially, for each i = 1, 2, 3, 4, cursor i points to the x_i-th character of S.

The machine \mathrm{M} has two buttons: the Abbreviation Button and the Update Button. Pressing these buttons triggers the following actions:

• Abbreviation Button: Machine \mathrm{M} outputs a string of length 4 formed by concatenating the characters pointed to by cursors 1, 2, 3, 4 in this order.
• Update Button: For each i = 1, 2, 3, 4, the following happens:
  • Let y be the current position of cursor i. Cursor i moves from the y-th character of S to the A_y-th character of S.

This year's programming contest abbreviation was determined by pressing the Abbreviation Button, resulting in TTPC. Here, "this year" refers to 0 years from now.

Starting from next year, the abbreviation for the programming contest each year will be obtained through the following steps:

1. Press the update button.
2. Press the abbreviation button to determine the abbreviation.

How many years from now will the abbreviation return to TTPC for the last time? Will the end of TTPC come?

Constraints

• N, A_i, x_1, x_2, x_3, x_4 are integers.
• 3 \leq N \leq 50
• S is a string of length N consisting of uppercase English letters.
• 1 \leq A_i \leq N\ (1 \leq i \leq N)
• 1 \leq x_1, x_2, x_3, x_4 \leq N
• S_{x_1} = {}T
• S_{x_2} = {}T
• S_{x_3} = {}P
• S_{x_4} = {}C

Sample Input 1

5
TTTPC
2 3 4 4 5
1 2 4 5

Sample Output 1

1

• 0 years from now, the abbreviation is TTPC, and the cursor positions are (1,2,4,5).
• 1 year from now, the abbreviation is TTPC, and the cursor positions are (2,3,4,5).
• 2 years from now, the abbreviation is TPPC, and the cursor positions are (3,4,4,5).
• 3 years from now, the abbreviation is PPPC, and the cursor positions are (4,4,4,5).

The last time the abbreviation becomes TTPC is 1 year from now.

Sample Input 2

4
TTPC
2 3 4 1
1 2 3 4

Sample Output 2

NeverEnds

The abbreviation becomes TTPC at years 0, 4, 8, 12, \dots and so on. TTPC never ends.

Sample Input 3

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

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, \cdots, A_N) of length N, consisting of 0, 1, and -1.

There are 2^q ways to replace all -1s in A with either 0 or 1, where q is the number of -1s in A. Among these, for all sequences that contain both 0 and 1, calculate the sum of the answers to the following problem modulo 998244353:

Let \alpha and \beta be the number of 0s and 1s in A, respectively.
Also, let X = (X_0, X_1, \cdots, X_{\alpha-1}) be the sequence of indices of A_i = 0, arranged in increasing order, and let Y = (Y_0, Y_1, \cdots, Y_{\beta-1}) be the sequence of indices of A_i = 1, arranged in increasing order (note that the indices of X and Y start from 0).

\displaystyle\sum_{i=0}^{\mathrm{LCM}(\alpha, \beta)-1} |X_{(i \bmod \alpha)} - Y_{(i \bmod \beta)}|

Calculate the value of the above expression.

Here, \mathrm{LCM}(x, y) represents the least common multiple of x and y, and x \bmod y denotes the remainder when x is divided by y.

Constraints

• All input values are integers.
• 2 \leq N \leq 2250
• Each A_i is either 0, 1, or -1 (i = 1, 2, \cdots, N).

Partial Score

• 30 points will be awarded for passing the test set satisfying the additional constraint N \leq 100.

Sample Input 1

4
1 1 -1 -1

Sample Output 1

14

For A = (1, 1, 0, 0), |3 - 1| + |4 - 2| = 4.
For A = (1, 1, 0, 1), |3 - 1| + |3 - 2| + |3 - 4| = 4.
For A = (1, 1, 1, 0), |4 - 1| + |4 - 2| + |4 - 3| = 6.
Thus, the answer is 4 + 4 + 6 = 14.

Sample Input 2

3
0 0 0

Sample Output 2

0

Since it is not possible to form a sequence containing both 0 and 1, the answer is 0.

Sample Input 3

10
-1 -1 0 -1 -1 1 -1 -1 -1 -1

Sample Output 3

10152

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

There are N \times M stones on a number line, with M colors labeled 1 through M, and N stones of each color. Here, N is an even number, and M is an odd number. Among the stones of color i, the j-th stone from the left (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) is initially placed at the coordinate (j-1) \times M + i. Stones of the same color are indistinguishable.

You can perform the following operation up to (N+1) \times M times:

Pick two adjacent stones and move them, in the same order, to any unoccupied adjacent positions.
Specifically:

1. Choose an integer x such that -10^9 \leq x \leq 10^9-1 and there are stones at both coordinates x and x+1. Let the stone at x be A and the stone at x+1 be B. Remove A and B from the number line.
2. Choose an integer y such that -10^9 \leq y \leq 10^9-1 and there are no stones at both coordinates y and y+1. Place A at y and B at y+1.

Your goal is to rearrange the stones to satisfy the following two conditions:

• All stones are part of a single contiguous block. That is, there exists an integer n such that for all integers x satisfying n \leq x \leq n + NM - 1, there is exactly one stone at coordinate x.
• Additionally, the stones are sorted by color in ascending order. Specifically, among the stones of color i, the j-th stone from the left (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) is at coordinate n + (i-1) \times N + (j-1).

Under the constraints of this problem, it can be shown that the goal is always achievable. Output one valid sequence of operations to achieve the goal. You do not need to minimize the number of operations.

Constraints

• 2 \leq N \leq 1000
• 3 \leq M \leq 999
• N is even
• M is odd

Sample Input 1

4 3

Sample Output 1

13
3 13
10 3
12 10
6 12
4 6
1 4
13 14
14 14
14 999999999
999999999 -1000000000
9 13
5 9
-1000000000 5

Initially, the stones are placed as follows (. indicates an unoccupied position). The coordinate of the leftmost . is 0, and the coordinate of the rightmost . is 15.

.123123123123...

After the first three operations, the stone arrangement changes as follows:

.123123123123...
↓
.12..2312312331.
↓
.121223123..331.
↓
.12122312333..1.

Finally, the stones are rearranged as follows:

...111122223333.

This arrangement satisfies the conditions of being a single contiguous block and sorted by color. Additionally, the number of operations is at most (N + 1) \times M = 15, so this output is valid.

Problem Statement

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

Alice and Bob play a game where they alternately mark vertices with their own markers. Initially, no vertices are marked.

First, Alice chooses any vertex and marks it with her marker. Then, starting with Bob, the two players alternate performing the following operation. The player who cannot make a move loses, and the other player wins.

• Choose a vertex v that satisfies the following conditions:
  • Vertex v is not marked.
  • There exists a vertex u connected to v by an edge such that u is marked with the opponent's marker.
• Mark the chosen vertex v with their own marker.

Determine the winner when both players adopt the optimal strategy for their own victory.

Constraints

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

Sample Input 1

5
1 2
2 3
3 4
2 5

Sample Output 1

Alice

For example, consider the following scenario:

1. Alice starts by marking vertex 1 with her marker.
2. Bob marks vertex 2 (vertex 1 is marked by the opponent and is connected to vertex 2 by an edge).
3. Alice marks vertex 3 (vertex 2 is marked by the opponent and is connected to vertex 3 by an edge).
4. Bob marks vertex 4 (vertex 3 is marked by the opponent and is connected to vertex 4 by an edge).
5. Alice marks vertex 5 (vertex 2 is marked by the opponent and is connected to vertex 5 by an edge).
6. Bob cannot make a move. Alice wins.

In this tree, Alice has a winning strategy, so you should output Alice.

Sample Input 2

4
1 2
3 4
3 2

Sample Output 2

Bob

Sample Input 3

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

Sample Output 3

Alice

Problem Statement

Shobon proposed the following problem:

Marunomi

You are given a sequence of positive integers W = (w_1, w_2, \dots, w_N).

There are N living slimes, named Slime 1, 2, \dots, N.
Initially, the weight of Slime i (1 \leq i \leq N) is w_i, and its number of victories is 0.

You can perform the following operation on the slimes zero or more times:

• Choose two living slimes, say Slime i and Slime j (i \neq j).
  • Let the current weight of Slime i be W_i and that of Slime j be W_j.
  • If W_i \gt W_j, the number of victories of Slime i increases by 1, its weight becomes W_i + W_j, and Slime j dies.
  • If this condition is not satisfied, nothing happens.

For each i = 1, 2, \dots, N, let S_i be the maximum number of victories Slime i can achieve through your actions.
Calculate the value of S_1 + S_2 + \dots + S_N.

However, since this problem is similar to ARC189 D - Takahashi is Slime, noya2 modified it as follows:

Marunomi for All Prefixes

You are given a sequence of positive integers A = (a_1, a_2, \dots, a_M).

For each i = 1, 2, \dots, M, compute the answer to the Marunomi problem when W = (a_1, a_2, \dots, a_i).

Solve this problem.

Constraints

• All input values are integers.
• 1 \leq M \leq 2 \times 10^5
• 1 \leq a_i \leq 10^9\ (1 \leq i \leq M)

Sample Input 1

5
1 2 3 5 20

Sample Output 1

0 1 3 7 11

Sample Input 2

3
1 1 1

Sample Output 2

0 0 0

Sample Input 3

10
17 3467 115 716 9070 32 12251 237 549 17

Sample Output 3

0 1 3 6 10 15 22 29 38 46