Problem Statement

For a string S consisting of uppercase English letters, let f(S) be the maximum number of times the following operation can be performed when it is repeated zero or more times.

• Choose one occurrence of the substring ARC and replace it with CRA.

For example, for S= ARARC, f(S)=2 (the operations ARARC \to ARCRA \to CRARA can be performed, and this is the maximum).

You are given an integer X between 0 and 600 (inclusive).

Find one string S consisting of uppercase English letters, of length between 1 and 100 (inclusive), satisfying f(S)=X.

It can be proved that such a string always exists under the constraints.

Constraints

• 0\le X\le 600
• The input value is an integer.

Sample Input 1

2

Sample Output 1

ARARC

S= ARARC is a string of length 5 consisting of uppercase English letters, satisfying f(S)=2. Thus, outputting ARARC will be accepted.

Besides this, ARCXXXARC, for example, will also be accepted.

Sample Input 2

0

Sample Output 2

ATCODER

Sample Input 3

3

Sample Output 3

ARARCDARC

Problem Statement

You are given a length-N sequence of non-negative integers A=(A_1,A_2,\dots,A_N).

You can perform the following operation on A any number of times, possibly zero:

• Choose a positive integer x_0, and set x=x_0. Then, for i=1,2,\ldots,N in this order, do the following:
  • Subtract x from A_i, and replace x with \displaystyle \left\lfloor \frac x2\right\rfloor.

Determine whether it is possible to make all elements of A equal to 0, and if it is possible, find the minimum number of operations required to do so.

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

Constraints

• 1\le T\le 10^4
• 1\le N\le 30
• 0\le A_i\le 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
-1
0
3

Consider the first test case.

By performing the operations as follows, you can make all elements of A equal to 0 in two operations:

• Choose x_0=3. A=(10,4) becomes A=(7,3).
• Choose x_0=7. A=(7,3) becomes A=(0,0).

It is impossible to make all elements of A equal to 0 in fewer than two operations, so output 2 on the first line.

Problem Statement

You are given a length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N).

Find the minimum possible value of \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor after rearranging A in any order.

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

Constraints

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

Sample Input 1

4
4
1 2 4 3
3
4 4 4
5
3 1 4 1 5
10
278117031 167642909 517897721 148434323 567739597 319926999 481642530 659199879 252516557 49913403

Sample Output 1

5
8
9
2829561210

Consider the first test case.

For example, rearranging A as (3,2,1,4) gives \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor=\left\lfloor\frac52\right\rfloor+\left\lfloor\frac32\right\rfloor+\left\lfloor\frac52\right\rfloor=5.

No matter how A is rearranged, the value of \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor is at least 5, so the answer is 5.

Problem Statement

There are K+1 piles of stones. The i-th pile has A_i stones.
Alice and Bob play a game. In this game, they alternately take turns with Alice moving first. On each turn, the following operation is performed exactly K times.

• Choose a pile with one or more stones, and remove one or more stones from it. Here, the same pile may be chosen multiple times within the same turn.

The player who is unable to perform the operation K times on their own turn loses the game. Which player wins when both players play optimally?

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

Constraints

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

Sample Input 1

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

Sample Output 1

Alice
Bob
Alice

Consider the first test case.
For example, suppose Alice performs the following operations on her first turn.

• Choose the second pile, and remove two stones from it. The number of stones in the second pile becomes 0.
• Choose the third pile, and remove three stones from it. The number of stones in the third pile becomes 0.

After her turn ends, only one stone remains. Therefore, Bob cannot perform the operation twice, so Alice wins.

In the second test case, every time Alice removes stones from one pile, Bob can remove the same number of stones from the other pile. By acting in this way, Bob can win.

Problem Statement

Takahashi is known for being able to split into the famous comedy duo "Taka and Hashi", that is, Taka and Hashi. When Taka and Hashi merge, they return to being the original Takahashi.
There is a connected undirected graph with N vertices and M edges, and each edge is labeled with 1, 2, or 3. The i-th edge connects vertices u_i and v_i, and is labeled l_i. The graph does not contain self-loops, but may contain multi-edges.
Each edge can be traversed by only one of Takahashi, Taka, and Hashi, and an edge labeled 1, 2, or 3 can be traversed only by Takahashi, Taka, or Hashi, respectively.

Initially, Takahashi is at vertex 1. Takahashi and the others can perform the following operations in any order, zero or more times.

• Takahashi splits into Taka and Hashi at the vertex where he currently is. At this point, both Taka and Hashi are at that vertex.
• One of the currently existing people moves by traversing one edge that they are able to traverse.
• When Taka and Hashi are at the same vertex, they merge at that vertex and return to being Takahashi.

Enumerate, in ascending order, all vertices where Takahashi can be after performing a sequence of operations.

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

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• 1 \leq l_i \leq 3
• The given graph is connected.
• The sum of N over all test cases is at most 2 \times 10^5.
• The sum of M over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

Consider the first test case.
Takahashi can move from vertex 1 to vertex 2 by traversing an edge labeled 1. After splitting into Taka and Hashi at vertex 2, Taka moves 2 \to 3 \to 4 and Hashi moves 2 \to 4, and by merging at vertex 4, it is possible to make Takahashi be at vertex 4. Furthermore, Takahashi can move to vertex 5 by traversing an edge labeled 1.
It is impossible to make Takahashi be at vertex 3, so the vertices satisfying the condition are 1,2,4,5.

Problem Statement

You are given a positive integer N and a length-N sequence of positive integers C=(C_1,C_2,\ldots,C_N).

You want to prepare one or more cards, as many as you like, and write one integer between 1 and N (inclusive) on each of the front and back sides of each card, so that the following condition is satisfied.

• No matter which distinct integers x and y between 1 and N (inclusive) are chosen, there exists at least one card satisfying the following.
  • Exactly one of x and y is written on at least one side of that card.

It is allowed to write the same integer on the front and back of a single card.

Here, the cost of writing a on the front and b on the back of a card is C_a+C_b.

Find the minimum total cost required to satisfy the condition.

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

Constraints

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

Sample Input 1

3
3
3 2 5
4
5 6 7 8
7
12 42 21 10 29 33 18

Sample Output 1

9
23
145

Consider the first test case.

By creating a card with 1 written on the front and 2 on the back, and a card with 2 written on the front and 2 on the back, the condition can be satisfied.

The total cost in this case is 3+2+2+2=9. It is impossible to satisfy the condition with a total cost less than 9, so output 9 on the first line.