Bajtazar has invented a certain permutation $P$ of numbers from $1$ to $n$. Bajtazar wants 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 you with answers to questions of the following form:

• $f(i, j, d)$: is the difference between the $i$-th and $j$-th elements of the permutation $P$ divisible by $d$, i.e., does $d \mid P[i] - P[j]$ hold?
• $g(i, j)$: is the $i$-th element of the permutation $P$ greater than the $j$-th element of the permutation $P$?

In the above questions, $i, j$ are any indices from the set $\{1, 2, \dots, n\}$, and $d$ is any positive integer.

During the guessing game, you may use questions of type $f$ as many times as you like, while the number of questions of type $g$ performed must be as small as possible.

Write a program that communicates with the library provided by Bajtazar to solve this puzzle.

Subtasks

Let $M(n)$ be the minimum possible number of questions of type $g$ required to find the $1$ in a permutation of a fixed length $n$, regardless of what that permutation is. Your program will receive points for a given test only if the number of questions of type $g$ it performs does not exceed $M(n)$. Furthermore, the program must fit within the time limit, and thus perform a reasonable number of questions of type $f$ (though not necessarily the minimum).

In all tests, the condition $1 \le n \le 500\,000$ holds. In tests worth $28\%$ of the points, the additional condition $n \le 5\,000$ holds.

Interaction

To use the library, you must include the following at the beginning of your program:

• C/C++: #include "cgdzlib.h"
• Pascal: uses pgdzlib;

The library provides the following functions and procedures:

• inicjuj – returns the number $n$. It should be used exactly once, at the very beginning of the program's execution.
  • C/C++: int inicjuj();
  • Pascal: function inicjuj: LongInt;
• f(i, j, d) – asks the Bajtazar library a question of type $f$. Its result is a single number: $1$ if $d \mid P[i] - P[j]$, and $0$ otherwise.
  • C/C++: int f(int i, int j, int d);
  • Pascal: function f(i, j, d : LongInt) : LongInt;
• g(i, j) – asks the Bajtazar library a question of type $g$. Its result is a single number: $1$ if $P[i] > P[j]$, and $0$ otherwise.
  • C/C++: int g(int i, int j);
  • Pascal: function g(i, j : LongInt) : LongInt;
• odpowiedz(k) – informs the Bajtazar library that the $1$ is located at the $k$-th position in the permutation (i.e., that $P[k] = 1$). Executing this procedure/function terminates your program.
  • C/C++: void odpowiedz(int k);
  • Pascal: procedure odpowiedz(k : LongInt);

Your program must not read any data (neither from standard input nor from files). It also must not write anything to files or standard output. It may write to the standard diagnostic output (stderr) – however, remember that this consumes valuable time.

Examples

Example 1

Note

After the second question, we know that $P[2] \neq 1$. Thus, after the third question, one of the possibilities holds: $(P[2] = 2, P[3] = 5)$ or $(P[2] = 4, P[3] = 1)$, or $(P[2] = 5, P[3] = 2)$. The fourth question eliminates the first of these possibilities. The fifth question now allows us to conclude that $P[1] \in \{3, 4\}$. Since in the sixth question we have $3 \mid P[1] - P[4]$, then $P[1] = 4, P[4] = 1$. The sought position in the permutation is $k = 4$.

The provided sequence of questions correctly finds the position of the $1$ in the permutation, however, it would not receive any points for this test, as in any permutation of five elements, the $1$ can be found using at most one question of type $g$ (i.e., $M(5) = 1$). Note that the number of questions of type $f$ performed does not play a role here.

Implementation Details

In the directory /home/zawodnik/rozw/gdz on the workstation, there is a sample library available that will allow you to test the formal correctness of your solution. The library reads the description of the permutation from standard input in the following format:

• in the first line, an integer $n$ – the length of the permutation;
• in the second line, $n$ space-separated integers from $1$ to $n$ – the consecutive elements of the permutation.

Sample input for the library is located in the file gdz0.in. After the program finishes, the library prints to standard output information about whether the answer provided by your solution was correct, and the number of questions of type $g$ asked.

In the same directory, there are sample solutions gdz.c, gdz.cpp, and gdz.pas that use the library. These solutions do not minimize the number of questions of type $g$.

To compile the solution together with the library, use the following commands:

• C: gcc -O2 -static cgdzlib.c gdz.c -lm -o gdz
• C++: g++ -O2 -static cgdzlib.c gdz.cpp -lm -o gdz
• Pascal: ppc386 -O2 -XS -Xt gdz.pas

The solution file and the library should be in the same directory.