Problem Statement

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

• N is an integer such that 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa

Problem Statement

One day, tired from going to school, Takahashi wanted to know how many days there were until Saturday.
We know that the day was a weekday, and the name of the day of the week was S in English.
How many days were there until the first Saturday after that day (including Saturday but not the starting day)?

Constraints

• S is Monday, Tuesday, Wednesday, Thursday, or Friday.

Sample Input 1

Wednesday

Sample Output 1

3

It was Wednesday, so there were 3 days until the first Saturday after that day.

Sample Input 2

Monday

Sample Output 2

5

Problem Statement

There are N balls. Each ball is painted in one of N colors: color 1 through color N. The color of the i-th ball (1\le i\le N) is C_i.

In one operation, you can change the color of any one ball to any of the N colors.

Find the minimum number of operations required to make all the balls the same color.

Constraints

• 1\le N\le 100
• 1\le C_i\le N
• All input values are integers.

Sample Input 1

4
3 1 2 1

Sample Output 1

2

By changing the color of the first ball to 1 and the color of the third ball to 1, you can make all the balls the same color.

It is impossible to make all the balls the same color by changing the colors of fewer than two balls, so output 2.

Sample Input 2

5
3 3 3 3 3

Sample Output 2

0

All balls may have the same color from the beginning.

Sample Input 3

9
4 2 3 3 4 1 2 7 1

Sample Output 3

7

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

A non-negative integer n is called a good integer when it satisfies the following condition:

• All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.

Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228

Problem Statement

Takahashi and Aoki will play the following game against each other.

Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.

In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.

Constraints

• 1 \leq N \leq 1000
• N is an integer.

Input and Output

This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.

First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.

1. Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
2. The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.

Notes

• After each output, you must flush Standard Output. Otherwise, you may get TLE.
• After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
• If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.

Sample Input and Output

Problem Statement

There is a two-dimensional coordinate plane. A lattice point with coordinates (x, y) is painted black if \max(|x|, |y|) is even, and white if it is odd.

Among the pairs of integers (x, y) satisfying L \leq x \leq R and D \leq y \leq U, find the number of those for which the point (x, y) is painted black.

Constraints

• -10^6 \leq L \leq R \leq 10^6
• -10^6 \leq D \leq U \leq 10^6
• All input values are integers.

Sample Input 1

-4 3 1 3

Sample Output 1

10

As shown in the figure above, the answer is 10.

Sample Input 2

-14 14 -14 14

Sample Output 2

449

Problem Statement

The Kingdom of AtCoder has N cities called City 1,2,\ldots,N and M roads called Road 1,2,\ldots,M.
Road i connects Cities A_i and B_i bidirectionally and has a length of C_i.
One can travel between any two cities using some roads.

Under financial difficulties, the kingdom has decided to maintain only N-1 roads so that one can still travel between any two cities using those roads and abandon the rest.

Let d_i be the total length of the roads one must use when going from City 1 to City i using only maintained roads. Print a choice of roads to maintain that minimizes d_2+d_3+\ldots+d_N.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i < B_i \leq N
• (A_i,B_i)\neq(A_j,B_j) if i\neq j.
• 1\leq C_i \leq 10^9
• One can travel between any two cities using some roads.
• All values in input are integers.

Sample Input 1

3 3
1 2 1
2 3 2
1 3 10

Sample Output 1

1 2

Here are the possible choices of roads to maintain and the corresponding values of d_i.

• Maintain Road 1 and 2: d_2=1, d_3=3.
• Maintain Road 1 and 3: d_2=1, d_3=10.
• Maintain Road 2 and 3: d_2=12, d_3=10.

Thus, maintaining Road 1 and 2 minimizes d_2+d_3.

Sample Input 2

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

Sample Output 2

3 1 2

Problem Statement

You are given a string S = S_1 S_2 S_3 \dots S_{|S|} consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string S are properly matched.

Repeat the following operation until no more operations can be performed:

• First, select one pair of integers (l, r) that satisfies all of the following conditions:
  • l < r
  • S_l = (
  • S_r = )
  • Each of the characters S_{l+1}, S_{l+2}, \dots, S_{r-1} is an uppercase or lowercase English letter.
• Let T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
  • Here, \overline{x} denotes the string obtained by toggling the case of each character in x (uppercase to lowercase and vice versa).
• Then, delete the l-th through r-th characters of S and insert T at the position where the deletion occurred.

Refer to the sample inputs and outputs for clarification.

It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.

Constraints

• 1 \le |S| \le 5 \times 10^5
• S consists of uppercase and lowercase English letters, (, and ).
• The parentheses in S are properly matched.

Sample Input 1

((A)y)x

Sample Output 1

YAx

Let us perform the operations for S = ((A)y)x.

• Choose l=2 and r=4. The substring (A) is removed and replaced with a.
  • After this operation, S = (ay)x.
• Choose l=1 and r=4. The substring (ay) is removed and replaced with YA.
  • After this operation, S = YAx.

After removing the parentheses, the string becomes YAx, which should be printed.

Sample Input 2

((XYZ)n(X(y)Z))

Sample Output 2

XYZNXYZ

Let us perform the operations for S = ((XYZ)n(X(y)Z)).

• Choose l=10 and r=12. The substring (y) is removed and replaced with Y.
  • After this operation, S = ((XYZ)n(XYZ)).
• Choose l=2 and r=6. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxn(XYZ)).
• Choose l=6 and r=10. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxnzyx).
• Choose l=1 and r=9. The substring (zyxnzyx) is removed and replaced with XYZNXYZ.
  • After this operation, S = XYZNXYZ.

After removing the parentheses, the string becomes XYZNXYZ, which should be printed.

Sample Input 3

(((()))(()))(())

Sample Output 3

The final outcome may be an empty string.

Sample Input 4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

Sample Output 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve