Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

• S is a string of length 4 consisting of 0 and 1.

Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.

Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111

Problem Statement

There is a bottle of disinfectant that can disinfect exactly M hands.

N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.

Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq H_i \leq 100
• All input values are integers.

Sample Input 1

5 10
2 3 2 5 3

Sample Output 1

3

The aliens disinfect their hands in the following steps:

• The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
• The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
• The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
• The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.

Thus, the first three aliens can disinfect all of their hands, so print 3.

Sample Input 2

5 10
2 3 2 3 5

Sample Output 2

4

Sample Input 3

1 5
1

Sample Output 3

1

All aliens can disinfect their hands.

Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

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

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

3

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

5

Problem Statement

For a positive integer X, let \text{ctz}(X) be the (maximal) number of consecutive zeros at the end of the binary notation of X.
If the binary notation of X ends with a 1, then \text{ctz}(X)=0.

You are given a positive integer N. Print \text{ctz}(N).

Constraints

• 1\leq N\leq 10^9
• N is an integer.

Sample Input 1

2024

Sample Output 1

3

2024 is 11111101000 in binary, with three consecutive 0s from the end, so \text{ctz}(2024)=3.
Thus, print 3.

Sample Input 2

18

Sample Output 2

1

18 is 10010 in binary, so \text{ctz}(18)=1.
Note that we count the trailing zeros.

Sample Input 3

5

Sample Output 3

0

Problem Statement

You are given a grid of H rows and W columns.
Let (i,j) denote the cell at row i (1 \leq i \leq H) from the top and column j (1 \leq j \leq W) from the left.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W, as follows:

• If the j-th character of S_i is #, cell (i,j) is painted black.
• If the j-th character of S_i is ., cell (i,j) is painted white.
• If the j-th character of S_i is ?, cell (i,j) is not yet painted.

Takahashi wants to paint each not-yet-painted cell white or black so that all the black cells form a rectangle.
More precisely, he wants there to exist a quadruple of integers (a,b,c,d) (1 \leq a \leq b \leq H, 1 \leq c \leq d \leq W) such that:

For each cell (i,j) (1 \leq i \leq H, 1 \leq j \leq W), if a \leq i \leq b and c \leq j \leq d, the cell is black;
otherwise, the cell is white.

Determine whether this is possible.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of #, ., ?.
• There is at least one cell that is already painted black.

Sample Input 1

3 5
.#?#.
.?#?.
?...?

Sample Output 1

Yes

The grid is in the following state. ? indicates a cell that are not yet painted.

By painting cells (1,3), (2,2), and (2,4) black and cells (3,1) and (3,5) white, the black cells can form a rectangle as follows:

Therefore, print Yes.

Sample Input 2

3 3
?##
#.#
##?

Sample Output 2

No

To form a rectangle with all black cells, you would need to paint cell (2,2) black, but it is already painted white.
Therefore, it is impossible to make all black cells form a rectangle, so print No.

Sample Input 3

1 1
#

Sample Output 3

Yes

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

• If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
• If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
• If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

• 2 \leq N \leq 10 ^ 9
• 1 \leq Q \leq 2\times10 ^ 5
• T _ i=1,2,3\ (1\leq i\leq Q)
• 1 \leq A _ i \leq N\ (1\leq i\leq Q)
• 1 \leq B _ i \leq N\ (1\leq i\leq Q)
• A _ i\neq B _ i\ (1\leq i\leq Q)
• There exists i\ (1\leq i\leq Q) such that T _ i=3.
• All values in the input are integers.

Sample Input 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

• User 1 follows user 2. No other users are following or followed by any users.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
• User 2 follows user 1.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
• User 2 follows user 3.
• User 3 follows user 2.
• Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
• User 1 unfollows user 2.
• Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

Sample Output 2

Yes
No

A user may follow the same user multiple times.

Sample Input 3

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

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Problem Statement

One day, Takahashi visited a cinema and decided to draw arrows on every floor tile, each pointing toward the nearest emergency exit.

You are given a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.
Each cell is represented by one of the following characters S_{i,j}:

• . : corridor cell
• # : wall cell
• E : emergency exit

For any corridor cell (i, j), define d(i, j), the distance to the nearest emergency exit, as follows:

• Starting from (i, j), repeatedly move to an adjacent non-wall cell in one of the four cardinal directions (up, down, left, right) until you reach an emergency exit. d(i, j) is the minimum number of moves required.

It is guaranteed that d(i, j) is definable for every corridor cell in the given grid; that is, every corridor cell (i, j) has at least one emergency exit reachable by passing through only corridor cells.

Write exactly one arrow (up, down, left, or right) in every corridor cell so that the following condition holds:

• For every corridor cell (i, j), if you start at (i, j) and perform the following action d(i, j) times, you reach an emergency exit:
  • Move one cell in the direction of the arrow written in your current cell. (You cannot move into a wall cell or outside the grid.)

Constraints

• 2 \le H \le 1000
• 2 \le W \le 1000
• Each S_{i,j} is ., #, or E.
• Every corridor cell (i, j) has at least one reachable emergency exit.
• H and W are integers.

Sample Input 1

3 4
...E
.#..
....

Sample Output 1

>>>E
^#>^
>>>^

Let us verify the condition for (2, 3) in the sample output. The distance from (2, 3) to the nearest emergency exit is 2, and following the arrows written in the sample output leads to an emergency exit in two moves.
The condition can be verified for every other corridor cell as well.

Sample Input 2

3 2
##
##
##

Sample Output 2

##
##
##

There may be cases with no corridor cells or emergency exits.

Sample Input 3

7 20
....................
..#..#..####..#E##..
..#..#..#..#..#.....
..E###..#..#..####..
.....#..#..E.....#..
.....#..####..####..
....................

Sample Output 3

>v<<<<<>>>>>>>>v<<<<
>v#^<#^^####v^#E##vv
>v#^<#v^#>v#vv#^<<<<
>>E###vv#>v#vv####^<
>>^<<#vv#>>E<<<<<#^<
>>^<<#vv####^<####^<
>>^<<<<<>>>>^<<<<<^<

Problem Statement

This problem is an interactive problem (in which your program and the judge system communicate via input and output).

You are given a tree G with N vertices numbered 1 to N. The i-th edge connects vertices U_i and V_i.

You will play a game with Takahashi using this tree G. First, you decide who is first and who is second. Then, starting from the first player, take turns performing the following operation:

• Choose a pair of integers (i,j) with 1 \leq i < j \leq N that satisfies both of the following conditions, then add an edge connecting vertices i and j to G.
  • G does not already have an edge connecting vertices i and j.
  • Adding an edge connecting vertices i and j does not create an odd cycle.

A player who cannot perform this operation loses, and the other player wins. Play this game against Takahashi and win.

Constraints

• 2 \leq N \leq 100
• 1 \leq U_i < V_i \leq N
• The given graph is a tree.
• All input values are integers.

Interaction

This is an interactive problem (in which your program and the judge system communicate via input and output).

First, read N and the edges of G from Standard Input, given in the following format:

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Then, decide whether you go first or second. If you choose first, print First; if second, print Second.

Then, the game begins.

On your turn, output the chosen pair (i,j) by printing two integers i and j in this order, separated by a space:

i j

On Takahashi's turn, two integers i,j will be given in order, separated by a space, via Standard Input:

i j

If (i,j)=(-1,-1), it means he can no longer make a move and you win. Immediately terminate your program in this case.
Otherwise, (i,j) is the pair of integers he has chosen.

Notes

• After each output, be sure to print a newline and flush Standard Output. Otherwise, you may get TLE.
• If you produce output in an incorrect format or your program ends prematurely, the judge result is indeterminate.
• Once the game finishes, terminate your program immediately. Otherwise, the judge result is indeterminate.

Sample Interaction

Problem Statement

There is a grid with N rows and N columns. We denote by (i, j) the square at the i-th (1 \leq i \leq N) row from the top and j-th (1 \leq j \leq N) column from the left.
Square (i, j) has a non-negative integer a_{i, j} written on it.

When you are at square (i, j), you can move to either square (i+1, j) or (i, j+1). Here, you are not allowed to go outside the grid.

Find the number of ways to travel from square (1, 1) to square (N, N) such that the exclusive logical sum of the integers written on the squares visited (including (1, 1) and (N, N)) is 0.

Constraints

• 2 \leq N \leq 20
• 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
• All values in the input are integers.

Sample Input 1

3
1 5 2
7 0 5
4 2 3

Sample Output 1

2

The following two ways satisfy the condition:

• (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3);
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3).

Sample Input 2

2
1 2
2 1

Sample Output 2

0

Sample Input 3

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

Sample Output 3

24307