Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

• 1 \leq V,A,B,C \leq 10^5
• All values in input are integers.

Sample Input 1

25 10 11 12

Sample Output 1

T

Now, they have 25 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 15.
• Next, Takahashi's mother uses 11 milliliters, leaving 4.
• Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

F

Now, they have 30 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 20.
• Next, Takahashi's mother uses 10 milliliters, leaving 10.
• Then, Takahashi uses 10 milliliters, leaving 0.
• Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

M

Problem Statement

You are given an integer K.

Print a string that is a concatenation of the first K uppercase English letters in ascending order, starting from A.

Constraints

• K is an integer between 1 and 26, inclusive.

Sample Input 1

3

Sample Output 1

ABC

The uppercase English letters in ascending order are A, B, C, ...

By concatenating the first three uppercase English letters, we get ABC.

Sample Input 2

1

Sample Output 2

A

Problem Statement

You are given strings S and T consisting of lowercase and uppercase English letters.

Determine whether the string S satisfies the following condition:

• Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

• Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.

Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.

Sample Input 3

abcde
XYZ

Sample Output 3

Yes

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

• We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

• All inputs are integers.
• 1 \le K < N \le 2 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from A=(3,1,5,4,9).

• For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
  • In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

You are given a tree with N vertices: vertex 1, vertex 2, \ldots, vertex N. The i-th edge (1\leq i\lt N) connects vertex u _ i and vertex v _ i.

Consider repeating the following operation some number of times:

• Choose one leaf vertex v and delete it along with all incident edges.

Find the minimum number of operations required to delete vertex 1.

Constraints

• 2\leq N\leq3\times10^5
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

The given graph looks like this:

For example, you can choose vertices 9,8,7,6,1 in this order to delete vertex 1 in five operations.

Vertex 1 cannot be deleted in four or fewer operations, so print 5.

Sample Input 2

6
1 2
2 3
2 4
3 5
3 6

Sample Output 2

1

In the given graph, vertex 1 is a leaf. Hence, you can choose and delete vertex 1 in the first operation.

Sample Input 3

24
3 6
7 17
7 20
7 11
14 18
17 21
6 19
5 22
9 24
11 14
6 23
8 17
9 12
4 17
2 15
1 17
3 9
10 16
7 13
2 16
1 16
5 7
1 3

Sample Output 3

12

Problem Statement

You are given a permutation P=(P_0,P_1,\ldots,P_{2^{N}-1}) of (1,2,3,\ldots,2^{N}).

You can perform the following operation any number of times (possibly zero):

• Choose non-negative integers a,b satisfying 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N}, and reverse P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}. Here, reversing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} means simultaneously replacing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} with P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}.

Find the lexicographically smallest permutation P that can be obtained by repeating the operation.

You are given T test cases, so find the answer for each.

Constraints

• 1 \leq T \leq 10^{5}
• 1 \leq N \leq 18
• P is a permutation of (1,2,3,\ldots,2^{N}).
• For each input file, the sum of 2^N over all test cases is at most 3 \times 10^{5}.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

In the first test case, when no operation is performed on P, P=(1,2). This is the lexicographically smallest permutation. Thus, the answer is (1,2).

In the second test case, when we perform the operation with a=1,b=1, P becomes (1,3,2,4). No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,3,2,4). Thus, the answer is (1,3,2,4).

In the third test case, by performing operations in the following order, we can obtain P=(1,4,2,3):

• Perform the operation with a=0,b=1. P becomes (3,2,4,1).
• Perform the operation with a=0,b=2. P becomes (1,4,2,3).

No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,4,2,3). Thus, the answer is (1,4,2,3).

Problem Statement

Snuke is planning to build a maze as a new attraction in AtCoder Land. The maze is represented as a grid with N rows and M columns, with the top edge of the top-right cell being the entrance and the bottom edge of the bottom-right cell being the exit. He will create the maze by appropriately placing walls between adjacent cells.

He loves simple mazes, so he wants the path from the entrance to the exit to pass through exactly K cells without any branches. Determine if it is possible to create such a maze, and if possible, construct one.

For example, in the following figure, N=3 and M=3, and walls are placed at the solid lines (walls are always placed around the outer perimeter except for the entrance and exit). In this case, the path from the entrance to the exit passes through exactly 7 cells without any branches.

Below is a formal statement.

There is a grid with N rows and M columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left. For each pair of side-adjacent cells, you can decide whether to place a wall between them. Determine whether it is possible to place walls to satisfy the following condition, and if it is possible, construct one such placement.

Consider an undirected graph G with NM vertices. Each vertex of G is uniquely labeled by a pair of integers (i,j)\ (1\leq i\leq N, 1\leq j\leq M). Two distinct vertices (i_1,j_1) and (i_2,j_2) are connected by an edge if and only if |i_1-i_2|+|j_1-j_2|=1 and there is no wall between the corresponding cells (i_1,j_1) and (i_2,j_2) on the grid.

Condition: there exists a simple path with K vertices that connects the two vertices (1,M) and (N,M), and the connected component containing the vertices (1,M) and (N,M) consists only of this path.

Constraints

• 2\leq N \leq 100
• 1\leq M \leq 100
• 1\leq K\leq NM
• All input values are integers.

Sample Input 1

3 3 7

Sample Output 1

Yes
+++++S+
+o.o.o+
+.+-+-+
+o.o.o+
+-+-+.+
+o.o|o+
+++++G+

This is the same placement of walls as in the figure in the problem statement.

Sample Input 2

3 3 2

Sample Output 2

No

Sample Input 3

4 1 4

Sample Output 3

Yes
+S+
+o+
+.+
+o+
+.+
+o+
+.+
+o+
+G+