Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

• N is an odd number between 1 and 99, inclusive.
• S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

Problem Statement

Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?

Constraints

• X and Y are integers.
• 1 \le X,Y \le 1000

Sample Input 1

80 94

Sample Output 1

2

• After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
• After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
• After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.

Sample Input 2

1000 63

Sample Output 2

0

The envelope may already have a stamp with enough value.

Sample Input 3

270 750

Sample Output 3

48

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N and a sequence B=(B_1,B_2,\dots,B_M) of length M. Here, all elements of A and B are pairwise distinct. Determine whether the sequence C=(C_1,C_2,\dots,C_{N+M}) formed by sorting all elements of A and B in ascending order contains two consecutive elements appearing in A.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq A_i, B_j \leq 200
• A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_M are distinct.
• All input values are integers.

Sample Input 1

3 2
3 2 5
4 1

Sample Output 1

Yes

C=(1,2,3,4,5). Since 2 and 3 from A occur consecutively in C, print Yes.

Sample Input 2

3 2
3 1 5
4 2

Sample Output 2

No

C=(1,2,3,4,5). Since no two elements from A occur consecutively in C, print No.

Sample Input 3

1 1
1
2

Sample Output 3

No

Problem Statement

From the point (0,0) in a two-dimensional plane, let us move the distance of 1 toward the point (A, B). Find our coordinates after the move.

Here, after moving the distance of d from a point X to a point Y (d \le length of the segment XY), we are at the point on the segment XY whose distance from X is d.
The Constraints guarantee that the distance between the points (0, 0) and (A, B) is at least 1.

Constraints

• All values in input are integers.
• 0 \le A,B \le 1000
• (A,B) \neq (0,0)

Sample Input 1

3 4

Sample Output 1

0.600000000000 0.800000000000

Printing 0.5999999999 0.8000000001, for example, would also be accepted.

Sample Input 2

1 0

Sample Output 2

1.000000000000 0.000000000000

We may arrive at (A, B).

Sample Input 3

246 402

Sample Output 3

0.521964870245 0.852966983083

Problem Statement

There is a queue of snakes. Initially, the queue is empty.

You are given Q queries, which should be processed in the order they are given. There are three types of queries:

• Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
• Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
• Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.

Constraints

• 1 \leq Q \leq 3 \times 10^{5}
• For a query of type 1, 1 \leq l \leq 10^{9}
• For a query of type 2, it is guaranteed that the queue is not empty.
• For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
• All input values are integers.

Sample Input 1

7
1 5
1 7
3 2
1 3
1 4
2
3 3

Sample Output 1

5
10

• 1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
• 2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
• 3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
• 4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
• 5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
• 6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
• 7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.

Sample Input 2

3
1 1
2
1 3

Sample Output 2

It is possible that there are no queries of type 3.

Sample Input 3

10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2

Sample Output 3

20
5

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

• Every integer i such that 0 \le i < m is contained in X.
• m is not contained in X.

Constraints

• All values in the input are integers.
• 1 \le K \le N \le 3 \times 10^5
• 0 \le A_i \le 10^9

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

• If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
• If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
• If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
• If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.

Problem Statement

There is a restaurant that can accommodate at most K customers simultaneously. In front of this restaurant, there is a side street where one queue is managed.

At time 0, there are no customers in the restaurant, and the queue is also empty.

Today, N groups of customers are scheduled to come, and they are numbered from 1 to N in the order of their arrival. Group i consists of C_i people, joins the end of the queue at time A_i, and leaves the restaurant B_i time units after entering.

Each group enters the restaurant by leaving the queue at the earliest time when both of the following two conditions are satisfied simultaneously:

• The group is at the front of the queue. In other words, the group is the earliest to have joined among those still in the queue at that point.
• When the number of people in that group and all groups currently in the restaurant (including those entering at exactly that time and excluding those leaving) are combined, there are K or fewer people.

Find the time when each group enters the restaurant.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq K \leq 10^7
• 1 \leq A_i, B_i \leq 10^7 (1 \leq i \leq N)
• A_1 < \dots < A_N
• 1 \leq C_i \leq K (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4 10
30 300 3
60 45 4
90 45 5
120 45 2

Sample Output 1

30
60
105
120

The entry and exit of each group proceed as follows:

• At time 30, group 1 joins the queue and immediately enters, making the number of customers in the restaurant 3.
• At time 60, group 2 joins the queue and immediately enters, making the number of customers in the restaurant 7.
• At time 90, group 3 joins the queue.
• At time 105, group 2 leaves, making the number of customers in the restaurant 3. Immediately after, group 3 enters, making the number of customers in the restaurant 8.
• At time 120, group 4 joins the queue and immediately enters, making the number of customers in the restaurant 10.
• At time 150, group 3 leaves, making the number of customers in the restaurant 5.
• At time 165, group 4 leaves, making the number of customers in the restaurant 3.
• At time 330, group 1 leaves, making the number of customers in the restaurant 0.

Sample Input 2

4 10
30 300 10
60 45 2
90 45 3
120 45 4

Sample Output 2

30
330
330
330

The entry and exit of each group proceed as follows:

• At time 30, group 1 joins the queue and immediately enters, making the number of customers in the restaurant 10.
• At time 60, group 2 joins the queue.
• At time 90, group 3 joins the queue.
• At time 120, group 4 joins the queue.
• At time 330, group 1 leaves, making the number of customers in the restaurant 0. Immediately after, groups 2,3,4 enter, making the number of customers in the restaurant 9.
• At time 375, groups 2,3,4 leave, making the number of customers in the restaurant 0.

Sample Input 3

10 24
279290 9485601 1
1094410 8022270 4
1314176 7214745 5
1897674 5924694 10
1921802 5769841 4
2506394 2765234 2
2558629 2727489 9
2681289 4061363 5
3022540 2291905 3
4407692 1313036 8

Sample Output 3

279290
1094410
1314176
1897674
1921802
7691643
7822368
8528921
8528921
10549857

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 of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).

Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:

• Placed in row i
• Placed in column j
• Placed on any square (a,b)\ (1\leq a\leq N,1\leq b\leq N) where i+j=a+b
• Placed on any square (a,b)\ (1\leq a\leq N,1\leq b\leq N) where i-j=a-b

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• 1\leq N\leq10^9
• 1\leq M\leq10^3
• 1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
• (a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on only two squares: squares (6,6) and (7,7).

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999997000000002

Out of 10^{18} squares, the squares that cannot be used are: squares in row 1, squares in column 1, and squares (1,1), (2,2), \ldots, (10^9,10^9), totaling 3\times10^9-2 squares.

Note that the answer may be 2^{32} or greater.

Sample Input 3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

Sample Output 3

77