Bajtazar has come up with a permutation $(P_0, P_1, \dots, P_{n-1})$ of numbers from $0$ to $n-1$. Bajtazar asks you to guess at which position in this permutation the number $1$ is located. To ensure you do not have to guess blindly, Bajtazar will provide answers to questions of the form: "What is the greatest common divisor of two different numbers $P_i$ and $P_j$?"

To make it not too simple, you can ask him at most $\lceil \frac{5n}{2} \rceil$ questions. Additionally, Bajtazar keeps coming up with new permutations, so you may have to search for the number $1$ many times.

Interaction

This is an interactive task. You must write a program that communicates with Bajtazar using the provided library. To do this, include the header gdzlib.h using the directive:

#include "gdzlib.h"

The library provides the following functions:

• int GetN() – Returns the parameter $n$ ($3 \le n \le 500\,000$ or $n = -1$). If $n \ge 3$, it denotes the length of the currently considered permutation. If $n = -1$, it means that Bajtazar has run out of permutations.
• int Ask(int i, int j) – Returns the greatest common divisor of the numbers $P_i$ and $P_j$ ($0 \le i, j < n, i \neq j$). In one test case, this function can be called at most $\lceil \frac{5n}{2} \rceil$ times.
• void Answer(int x) – Provides the answer that $P_x = 1$ ($0 \le x < n$).

Each execution of your program consists of at least one test case. Each case must be started with the GetN() function and ended with the Answer() function. Using the Ask() or Answer() function when no test case is active will result in a "wrong answer" verdict. After processing the last test case, the GetN() function will return $-1$. You should then terminate your program.

Test cases during a single program execution may have different parameters $n$. However, the sum of the lengths of the permutations during the program's operation will not exceed $500\,000$.

Using any function with incorrect arguments will result in a "wrong answer" verdict. Deliberate attempts to influence the internal operation of the grading library are prohibited.

Library

The library with which your program communicates may be malicious. This means that the library may adjust the hidden permutations depending on your queries.

The execution time of the library and the memory it uses may depend on the test and the exact behavior of your program. For this reason, the limits on SIO are slightly higher than those given in the problem statement. If the grading library runs faster or uses less memory than the allocated buffer, your program will be slightly less restricted.

Examples

Input 1

5
4 2 0 3 1
-1

Output 1

GetN()
Ask(1, 4)
Ask(1, 0)
Ask(2, 3)
Answer(4)
GetN()

Note 1

In the example test, there is only one test case. The value of $n$ is $5$, and the hidden permutation $P$ is $(4, 2, 0, 3, 1)$.

Bajtazar asked $3$ Ask() queries, which is within the limit of $\lceil \frac{5n}{2} \rceil = 13$ queries. Remember that queries are counted separately for each test case.

Implementation Details

A sample incorrect solution and a sample library can be found in the archive in the Files section on SIO. The library may differ in behavior from the one that will be used to evaluate solutions and may not meet the assumptions of the task. It is only intended to show how to interact with the program.

The solution gdz.cpp can be compiled as follows:

g++ -O3 -static -o gdz gdz.cpp gdzlib.cpp -std=c++17

Ensure that the files gdzlib.h and gdzlib.cpp are in the same folder as the solution.

After compilation, the library accepts descriptions of subsequent test cases on standard input. The description of each test should consist of two lines. The first one should contain a single number $n$. The second one should contain a permutation of numbers from $0$ to $n-1$. After the description of all test cases, there should be a line containing the number $-1$. The input file corresponding to the example test is in the archive in the file gdz0.in.