Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

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

You are given positive integers A and B.

You will repeat the following operation until A=B:

• compare A and B to perform one of the following two:
  • if A > B, replace A with A-B;
  • if A < B, replace B with B-A.

How many times will you repeat it until A=B? It is guaranteed that a finite repetition makes A=B.

Constraints

• 1 \le A,B \le 10^{18}
• All values in the input are integers.

Sample Input 1

3 8

Sample Output 1

4

Initially, A=3 and B=8. You repeat the operation as follows:

• A<B, so replace B with B-A=5, making A=3 and B=5.
• A<B, so replace B with B-A=2, making A=3 and B=2.
• A>B, so replace A with A-B=1, making A=1 and B=2.
• A<B, so replace B with B-A=1, making A=1 and B=1.

Thus, you repeat it four times.

Sample Input 2

1234567890 1234567890

Sample Output 2

0

Note that the input may not fit into a 32-bit integer type.

Sample Input 3

1597 987

Sample Output 3

15

Problem Statement

Let us play a game using a die. The game consists of at most N turns, each of which goes as follows.

• Throw a 6-sided die that shows 1,\ldots,6 with equal probability, and let X be the number shown (each throw is independent of the others).
• If it is the N-th turn now, your score is X, and the game ends.
• Otherwise, choose whether to continue or end the game.
  • If you end the game, your score is X, and there is no more turn.

Find the expected value of your score when you play the game to maximize this expected value.

Constraints

• 1 \leq N \leq 100

Sample Input 1

1

Sample Output 1

3.5000000000

Sample Input 2

2

Sample Output 2

4.2500000000

Sample Input 3

10

Sample Output 3

5.6502176688

Problem Statement

There is a directed graph with N vertices and M edges. Each edge has two positive integer values: beauty and cost.

For i = 1, 2, \ldots, M, the i-th edge is directed from vertex u_i to vertex v_i, with beauty b_i and cost c_i. Here, the constraints guarantee that u_i \lt v_i.

Find the maximum value of the following for a path P from vertex 1 to vertex N.

• The total beauty of all edges on P divided by the total cost of all edges on P.

Here, the constraints guarantee that the given graph has at least one path from vertex 1 to vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• 1 \leq b_i, c_i \leq 10^4
• There is a path from vertex 1 to vertex N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.7500000000000000

For the path P that passes through the 2-nd, 6-th, and 7-th edges in this order and visits vertices 1 \rightarrow 3 \rightarrow 4 \rightarrow 5, the total beauty of all edges on P divided by the total cost of all edges on P is (b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75, and this is the maximum possible value.

Sample Input 2

3 3
1 3 1 1
1 3 2 1
1 3 3 1

Sample Output 2

3.0000000000000000

Sample Input 3

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

Sample Output 3

1.8333333333333333