Problem Statement

You are given N strings S_1,S_2,\ldots,S_N in this order.

Print S_N,S_{N-1},\ldots,S_1 in this order.

Constraints

• 1\leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters, uppercase English letters, and digits.

Sample Input 1

3
Takahashi
Aoki
Snuke

Sample Output 1

Snuke
Aoki
Takahashi

We have N=3, S_1= Takahashi, S_2= Aoki, and S_3= Snuke.

Thus, you should print Snuke, Aoki, and Takahashi in this order.

Sample Input 2

4
2023
Year
New
Happy

Sample Output 2

Happy
New
Year
2023

The given strings may contain digits.

Problem Statement

You are given a real number X, which is representable using at most three decimal digits, with three decimal digits.
Round X to the nearest integer and print the result.

Constraints

• 0 \leq X < 100
• X is representable using at most three decimal digits.
• X has three decimal digits in input.

Sample Input 1

3.456

Sample Output 1

3

The digit in the first decimal place of 3.456 is 4, so we should round it down to 3.

Sample Input 2

99.500

Sample Output 2

100

Sample Input 3

0.000

Sample Output 3

0

Problem Statement

N players played a round-robin tournament.

You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.

Determine whether the given table is contradictory.

The table is said to be contradictory when some of the following holds:

• There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
• There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
• There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.

Constraints

• 2 \leq N \leq 1000
• A_{i,i} is -.
• A_{i,j} is W, L, or D, for i\neq j.

Sample Input 1

4
-WWW
L-DD
LD-W
LDW-

Sample Output 1

incorrect

Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.

Sample Input 2

2
-D
D-

Sample Output 2

correct

There is no contradiction.

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

• L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
• \displaystyle \sum_{i=1}^N X_i = 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq L_i \leq R_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9

Problem Statement

There are N dominoes standing in a row on a number line. The i-th domino is standing at coordinate i and has height A_i.

When the i-th domino falls to the right, all dominoes in the range between coordinates i and i+A_i-1, inclusive, fall to the right.

How many dominoes will fall in total when the first domino falls to the right?

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq N
• All input values are integers.

Sample Input 1

4
3 1 4 1

Sample Output 1

4

When the first domino falls to the right, the second and third dominoes also fall to the right. When the third domino falls to the right, the fourth domino also falls.

Sample Input 2

9
1 4 1 4 2 1 3 5 6

Sample Output 2

1

When the first domino falls to the right, no other dominoes will fall.

Sample Input 3

10
5 4 3 2 1 1 2 3 4 5

Sample Output 3

5

Problem Statement

This is an interactive task, where your program and the judge interact via Standard Input and Output.

The judge has a string of length N consisting of 0 and 1: S = S_1S_2\ldots S_N. Here, S_1 = 0 and S_N = 1.

You are given the length N of S, but not the contents of S. Instead, you can ask the judge at most 20 questions as follows.

• Choose an integer i such that 1 \leq i \leq N and ask the value of S_i.

Print an integer p such that 1 \leq p \leq N-1 and S_p \neq S_{p+1}.
It can be shown that such p always exists under the settings of this problem.

Constraints

• 2 \leq N \leq 2 \times 10^5

Input and Output

First, receive the length N of the string S from Standard Input:

N

Then, you get to ask the judge at most 20 questions as described in the problem statement.

Print each question to Standard Output in the following format, where i is an integer satisfying 1 \leq i \leq N:

? i

In response to this, the value of S_i will be given from Standard Input in the following format:

S_i

Here, S_i is 0 or 1.

When you find an integer p satisfying the condition in the problem statement, print it in the following format, and immediately quit the program:

! p

If multiple solutions exist, you may print any of them.

Notes

• Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
• If there is malformed output during the interaction or your program quits prematurely, the verdict will be indeterminate.
• After printing the answer, immediately quit the program. Otherwise, the verdict will be indeterminate.
• The string S will be fixed at the start of the interaction and will not be changed according to your questions or other factors.

Sample Input and Output

In the following interaction, N = 7 and S = 0010011.

For the presented p = 5, we have 1 \leq p \leq N-1 and S_p \neq S_{p+1}. Thus, if the program immediately quits here, this case will be judged as correctly solved.

Problem Statement

Given is a weighted undirected connected graph G with N vertices and M edges, which may contain self-loops and multi-edges.
The vertices are labeled as Vertex 1, Vertex 2, \dots, Vertex N.
The edges are labeled as Edge 1, Edge 2, \ldots, Edge M. Edge i connects Vertex a_i and Vertex b_i and has a weight of c_i. Here, for every pair of integers (i, j) such that 1 \leq i \lt j \leq M, c_i \neq c_j holds.

Process the Q queries explained below.
The i-th query gives a triple of integers (u_i, v_i, w_i). Here, for every integer j such that 1 \leq j \leq M, w_i \neq c_j holds.
Let e_i be an undirected edge that connects Vertex u_i and Vertex v_i and has a weight of w_i. Consider the graph G_i obtained by adding e_i to G. It can be proved that the minimum spanning tree T_i of G_i is uniquely determined. Does T_i contain e_i? Print the answer as Yes or No.

Note that the queries do not change T. In other words, even though Query i considers the graph obtained by adding e_i to G, the G in other queries does not have e_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N - 1 \leq M \leq 2 \times 10^5
• 1 \leq a_i \leq N (1 \leq i \leq M)
• 1 \leq b_i \leq N (1 \leq i \leq M)
• 1 \leq c_i \leq 10^9 (1 \leq i \leq M)
• c_i \neq c_j (1 \leq i \lt j \leq M)
• The graph G is connected.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq u_i \leq N (1 \leq i \leq Q)
• 1 \leq v_i \leq N (1 \leq i \leq Q)
• 1 \leq w_i \leq 10^9 (1 \leq i \leq Q)
• w_i \neq c_j (1 \leq i \leq Q, 1 \leq j \leq M)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

Below, let (u,v,w) denote an undirected edge that connects Vertex u and Vertex v and has the weight of w. Here is an illustration of G:

For example, Query 1 considers the graph G_1 obtained by adding e_1 = (1,3,1) to G. The minimum spanning tree T_1 of G_1 has the edge set \lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace, which contains e_1, so Yes should be printed.

Sample Input 2

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

Sample Output 2

Yes
No

Problem Statement

A robot is at the origin of a coordinate plane where the positive x-axis points to the right and the positive y-axis points upwards. Initially, the robot is facing the positive x-direction.

You will perform the following operation for i=1,\ldots,N in this order.

• Rotate the robot 90 degrees clockwise or counterclockwise. Then, the robot moves forward A_i units in the direction it is facing.

Can the direction of rotation be chosen so that the robot will be at the coordinates (X,Y) after the N operations?

If it is possible, determine which direction, clockwise or counterclockwise, should be chosen for each operation.

Constraints

• 1 \leq N \leq 80
• 1 \leq A_i \leq 10^7
• -10^9\leq X,Y \leq 10^9
• All input values are integers.

Sample Input 1

3 -2 4
3 2 1

Sample Output 1

Yes
LLR

Initially, the robot is at (0,0) and facing the positive x-direction. The following choices can put the robot at the coordinates (X,Y) after the N operations.

• First operation: Rotate the robot 90 degrees counterclockwise to face the positive y-direction. The robot moves forward A_1=3 units in the direction it is facing, and moves to (0,3).
• Second operation: Rotate the robot 90 degrees counterclockwise to face the negative x-direction. The robot moves forward A_2=2 units in the direction it is facing, and moves to (-2,3).
• Third operation: Rotate the robot 90 degrees clockwise to face the positive y-direction. The robot moves forward A_3=1 unit in the direction it is facing, and moves to (-2,4).

Sample Input 2

1 0 0
1

Sample Output 2

No

Sample Input 3

4 0 0
1 1 1 1

Sample Output 3

Yes
LRRR

Outputs such as LLLL and RRRR are also accepted.

Sample Input 4

14 2543269 -1705099
3 14 159 2653 58979 323846 2643383 2795028 841971 69399 37510 58 20 9

Sample Output 4

Yes
LLLLLLLLLRLRRR