Y has a sequence $\{a_n\}$ of length $n$, initially $\forall 1\le i\le n, a_i=i$.

He can perform the following operation several times, with the goal of transforming the sequence into another given sequence $\{b_n\}$, i.e., $\forall 1\le i\le n, a_i=b_i$. It is guaranteed that $\{b_n\}$ is a permutation of $1$ to $n$.

1. Choose $i, j$ such that $1\le i, j\le n, i\neq j, 2|a_i$.
2. Let $x=a_i/2$, then set $a_j$ to $a_j+x$ and $a_i$ to $a_i-x$.

Y wants to know if his goal can be achieved in a finite number of steps. If it can, please provide an operation sequence with a number of steps that is not too large.

Note that you do not need to minimize the number of steps; as long as you correctly determine whether a solution exists, provide a valid sequence of operations, and the number of steps does not exceed a given value $M$, your answer will be considered correct. Specific limits can be found in the Constraints section. You must also ensure that during the operations, all values in the sequence remain within $[1, 10^9]$. It can be proven that if a solution exists, at least one valid sequence can be found under the given constraints.

To avoid large output volumes, this problem uses an interactive format.

Implementation Details

You need to implement the function void SEQ(int n, int M), where $n$ and $M$ have the same meanings as in the problem statement.

You can obtain the value of $b[x]$ by calling int Get(int x). You are allowed to call this for the same $x$ multiple times, but you must ensure $1\le x\le n$.

Next, you must call the function void answer(int flag) exactly once, indicating whether you have determined if a solution exists. Use flag=1 to indicate that a solution exists, and flag=0 to indicate that no solution exists. If a solution exists, you need to call void add(int i, int j) several times to represent the operations $(i, j)$.

Please pay attention to the order of function calls.

Local Testing

Place all provided files in the same directory, compile using g++ sample-grader.cpp seq.cpp -o seq in the terminal, and run using ./seq < seq.in.

You can write your program based on the sample program sample-seq.cpp.

It is guaranteed that in each test case, the interaction library will call the function SEQ exactly once.

Examples

Input 1

5 10000000 1
4 2 5 1 3

Output 1

(The interaction process)

Note

This case has a solution. One possible sequence of operations is: $(i, j) = (4, 3), (4, 5), (5, 1)$.

The sequence $\{a_n\}$ changes as follows: 1 2 3 4 5 $\rightarrow$ 1 2 5 2 5 $\rightarrow$ 1 2 5 1 6 $\rightarrow$ 4 2 5 1 3.

Constraints

For all test cases, it is guaranteed that $1\le n\le 10^5$ and $1.5\times 10^6\le M\le 1.5\times 10^7$.

It is guaranteed that for test cases with $n > 1000$, $\{b_n\}$ is generated randomly.

• Subtask 1 (17 pts): $1\le n\le 10, M=10^7$.
• Subtask 2 (7 pts): $1\le n\le 150, \forall 1\le i\le n, b_i\equiv (i-1)\pmod n$.
• Subtask 3 (14 pts): $1\le n\le 150$.
• Subtask 4 (16 pts): $1\le n\le 1000, M=1.5\times 10^7$.
• Subtask 5 (16 pts): $1\le n\le 5000, M=1.5\times 10^7$.
• Subtask 6 (30 pts): $1\le n\le 10^5, M=1.5\times 10^7$.

There may be valid dependencies between subtasks.

It is guaranteed that the only difference between the final interaction library and the provided one is the addition of an anti-cheating mechanism, and there may be differences in input/output formats (however, your program should not produce any output, nor should it implement any main function).