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 two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

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

Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.

Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3

Problem Statement

You are given N circles on the xy-coordinate plane. For each i = 1, 2, \ldots, N, the i-th circle is centered at (x_i, y_i) and has a radius of r_i.

Determine whether it is possible to get from (s_x, s_y) to (t_x, t_y) by only passing through points that lie on the circumference of at least one of the N circles.

Constraints

• 1 \leq N \leq 3000
• -10^9 \leq x_i, y_i \leq 10^9
• 1 \leq r_i \leq 10^9
• (s_x, s_y) lies on the circumference of at least one of the N circles.
• (t_x, t_y) lies on the circumference of at least one of the N circles.
• All values in input are integers.

Sample Input 1

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

Sample Output 1

Yes

Here is one way to get from (0, -2) to (3, 3).

• From (0, -2), pass through the circumference of the 1-st circle counterclockwise to reach (1, -\sqrt{3}).
• From (1, -\sqrt{3}), pass through the circumference of the 2-nd circle clockwise to reach (2, 2).
• From (2, 2), pass through the circumference of the 3-rd circle counterclockwise to reach (3, 3).

Thus, Yes should be printed.

Sample Input 2

3
0 1 0 3
0 0 1
0 0 2
0 0 3

Sample Output 2

No

It is impossible to get from (0, 1) to (0, 3) by only passing through points on the circumference of at least one of the circles, so No should be printed.

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1,\ldots,N. For each i=1,\ldots,M, the i-th edge connects Vertex a_i and Vertex b_i. Additionally, the degree of each vertex is at most 3.

For each i=1,\ldots,Q, answer the following query.

• Find the sum of indices of vertices whose distances from Vertex x_i are at most k_i.

Constraints

• 1 \leq N \leq 1.5 \times 10^5
• 0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})
• 1 \leq a_i \lt b_i \leq N
• (a_i,b_i) \neq (a_j,b_j), if i\neq j.
• The degree of each vertex in the graph is at most 3.
• 1 \leq Q \leq 1.5 \times 10^5
• 1 \leq x_i \leq N
• 0 \leq k_i \leq 3
• All values in input are integers.

Sample Input 1

6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3

Sample Output 1

1
20
2
20
7
6
20

For the 1-st query, the only vertex whose distance from Vertex 1 is at most 1 is Vertex 1, so the answer is 1.
For the 2-nd query, the vertices whose distances from Vertex 2 are at most 2 are Vertex 2, 3, 4, 5, and 6, so the answer is their sum, 20.
The 3-rd and subsequent queries can be answered similarly.

Problem Statement

2^N people, numbered 1 to 2^N, will participate in a rock-paper-scissors tournament.

The tournament proceeds as follows:

• The participants are arranged in a row in the order Person 1, Person 2, \ldots, Person 2^N from left to right.
• Let 2M be the current length of the row. For each i\ (1\leq i \leq M), the (2i-1)-th and (2i)-th persons from the left play a game against each other. Then, the M losers are removed from the row. This process is repeated N times.

Here, if Person i wins exactly j games, they receive C_{i,j} yen (Japanese currency). A person winning zero games receives nothing. Find the maximum possible total amount of money received by the 2^N people if the results of all games can be manipulated freely.

Constraints

• 1 \leq N \leq 16
• 1 \leq C_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2
2 5
6 5
2 1
7 9

Sample Output 1

15

The initial row of the people is (1,2,3,4).

If Person 2 wins the game against Person 1, and Person 4 wins the game against Person 3, the row becomes (2,4).

Then, if Person 4 wins the game against Person 2, the row becomes (4), and the tournament ends.

Here, Person 2 wins exactly 1 game, and Person 4 wins exactly 2 games, so they receive 0+6+0+9=15 yen in total, which is the maximum possible sum.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 2

4