Problem Statement

There is a road of length L extending left and right. There are N zombies on this road, and the i-th zombie is at a distance of A_i from the left end of the road. Here, L and all A_i are even.

You have K pieces of bait for the zombies, and you can place a piece of bait at any position on the road, including both ends, at any time. However, there must never be a moment when two or more pieces of bait exist on the road simultaneously. When bait exists on the road, each zombie moves toward the bait at a speed of 1 per unit time. When one or more zombies reach the same position as the bait, the bait is eaten and disappears instantly.

When no bait exists on the road, zombies do not move. Find the maximum total amount of time bait exists on the road when the times and positions to place the bait are chosen optimally. It can be proved that the answer is an integer.

You are given T test cases; solve each one.

Constraints

• 1 \le T \le 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le K \le 10^9
• 2 \le L \le 10^9
• 0 \le A_i \le L
• L is even.
• All A_i are even.
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
2 2 20
4 18
8 9 14
0 2 4 6 8 10 12 14
3 3 140
120 70 20

Sample Output 1

18
40
160

For the first test case, it is optimal to place the bait as follows.

• First, place bait at position 11. The two zombies simultaneously reach position 11 after 7 units of time and eat the bait.
• Then, place bait at position 0. The two zombies simultaneously reach position 0 after 11 units of time and eat the bait.

The total amount of time bait exists on the road is 7 + 11 = 18.

Problem Statement

There are 2N gems arranged in a row from left to right, and the type of the i-th gem from the left is A_i. Here, A_i is an integer between 1 and N, inclusive, and there are exactly two gems of each type.

You want to insert dividers satisfying the following conditions.

• Each divider's position is represented by an integer i (1 \le i \le 2N - 1), meaning it divides between the i-th and (i+1)-th gems from the left.
• No two or more dividers exist at the same position.
• The number of dividers K is at most N.
• Inserting K dividers divides the row of gems into K + 1 segments. Here, collecting all gems in the odd-numbered (first, third, ...) segments from the left yields exactly one gem of each type 1, 2, \ldots, N.

Output one way to insert dividers satisfying this condition. It can be proved that such a way always exists.

You are given T test cases; solve each one.

Constraints

• 1 \le T \le 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le N (1 \le i \leq 2N)
• There are exactly two gems of each type. That is, for each x (1 \le x \le N), there are exactly two indices i with A_i = x.
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
1 2 4
1
5

For the first test case, inserting dividers at positions 1, 2, 4 divides the gems into segments (1),(2),(2,3),(3,1), and collecting all gems in the odd-numbered segments from the left yields exactly one gem of each type 1, 2, 3.

Problem Statement

There are N people with distinct surnames, and the surname of the i-th person has parameters (X_i, Y_i, Z_i). Different surnames may have identical parameters. The following event occurs N - 1 times.

• Two people become parents and one child appears. The two parents die. The child chooses the stronger of the two parents' surnames as their own. A surname with parameters (x_1, y_1, z_1) is stronger than a surname with parameters (x_2, y_2, z_2) if x_1 > x_2, y_1 > y_2, and z_1 > z_2 all hold. If neither parent's surname is stronger than the other's, the child randomly chooses one of the two parents' surnames.

Find the number of people among the N people whose surname can be the surname of the last remaining person.

You are given T test cases; solve each one.

Constraints

• 1 \le T \le 2 \times 10^5
• 2 \le N \le 2 \times 10^5
• 1 \le X_i, Y_i, Z_i \le N
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
3
2

For the first test case, below is a possible sequence of events.

Let surname i denote the surname of the i-th person.

• The people with surnames 2 and 4 become parents. Surname 2 is stronger, so the child has surname 2.
• The people with surnames 2 and 3 become parents. Surname 3 is stronger, so the child has surname 3.
• The people with surnames 1 and 3 become parents. Neither surname 1 nor surname 3 is stronger than the other, so the child chooses either surname 1 or 3.

Neither surname 2 nor surname 4 can be the surname of the last remaining person, so the answer is 2.

Problem Statement

For a sequence A = (A_1, A_2, \ldots, A_{N+1}) of length N+1, consider obtaining a sequence S = (S_1, S_2, \ldots, S_N) of length N in the following way.

• For each i (1 \le i \le N), let S_i = A_i + A_{i+1}.

Find the number, modulo 10^9 + 7, of sequences S of length N satisfying all of the following conditions.

• S is non-decreasing.
• There exists a sequence A of length N+1 consisting of integers between 0 and M, inclusive, such that S can be obtained from A in the way described above.

Constraints

• 1 \le N, M \le 10^7
• All input values are integers.

Sample Input 1

2 1

Sample Output 1

5

The possible sequences A are the following eight:

• A = (0,0,0), for which S = (0,0)
• A = (0,0,1), for which S = (0,1)
• A = (0,1,0), for which S = (1,1)
• A = (0,1,1), for which S = (1,2)
• A = (1,0,0), for which S = (1,0)
• A = (1,0,1), for which S = (1,1)
• A = (1,1,0), for which S = (2,1)
• A = (1,1,1), for which S = (2,2)

Among these, we have five distinct non-decreasing S: (0,0),(0,1),(1,1),(1,2),(2,2).

Sample Input 2

869121 10000000

Sample Output 2

767557322

Problem Statement

You are given binary strings A = A_1 A_2 \ldots A_N and B = B_1 B_2 \ldots B_N of length N.

You can perform M types of operations. The i-th type of operation is represented by a pair of integers (x_i, y_i) with 1 \le x_i, y_i \le N, and it flips the value of A_{y_i} when A_{x_i} = 1. It is possible that x_i = y_i. Here, flipping means changing 0 to 1 or 1 to 0.

Determine whether it is possible to convert A into a string equal to B by performing at most 2N operations on A, and if so, construct one such way.

You are given T test cases; solve each one.

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• A and B are binary strings of length N.
• A \neq B
• 1 \le x_i \le N (1 \le i \le M)
• 1 \le y_i \le N (1 \le i \le M)
• The sum of N and M over all test cases is at most 2 \times 10^5.
• T, N, M, x_i, y_i are integers.

Sample Input 1

3
4
0100
1010
4
1 2
2 1
2 3
4 3
2
10
01
1
1 2
2
01
00
3
1 1
1 2
2 1

Sample Output 1

3
2 3 1
-1
3
3 2 1

For the first test case, you can perform the operations as follows.

• Initially, A = 0100.
• Perform operation 2. Now, A = 1100.
• Perform operation 3. Now, A = 1110.
• Perform operation 1. Now, A = 1010.

For the second test case, no matter what operations are performed, it is impossible to make A_1 equal to 0.

Note that, as in the third test case, x_i = y_i is possible.

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge (1 \le i \le N - 1) connects vertices A_i and B_i. For a path in this tree, define the score of the path as the distance from the path to the farthest vertex. Here, the distance from a path is defined as the minimum distance to a vertex on the path.

A path with the minimum score is called a good path.

For each k = 1, 2, \ldots, N, find the number of good paths with exactly k vertices. Paths are distinguished only if their vertex sets differ.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le A_i < B_i \le N (1 \le i \le N - 1)
• The given graph is a tree.
• All input values are integers.

Sample Input 1

5
1 2
2 3
2 4
3 5

Sample Output 1

0
1
3
2
0

The minimum score is 1.

The good paths are the following six paths.

• The path with two vertices connecting vertices 2 and 3
• The path with three vertices connecting vertices 1 and 3
• The path with three vertices connecting vertices 2 and 5
• The path with three vertices connecting vertices 3 and 4
• The path with four vertices connecting vertices 1 and 5
• The path with four vertices connecting vertices 4 and 5

Sample Input 2

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

Sample Output 2

1
3
7
8
5
0
0
0

Sample Input 3

5
1 2
2 3
3 4
4 5

Sample Output 3

0
0
0
0
1