This is an interactive problem.

Alice has an integer $y \in [1, 10^{18}]$, and Bob wants to find this number. Bob can ask Alice questions by choosing an integer $x \in [0, 10^{18}]$. If $y > x$, Alice returns $2$; if $y = x$, Alice returns $1$; if $y < x$, Alice returns $0$.

However, the communication between Alice and Bob is intercepted by Eve. Eve has written a pseudo-random number generator:

const long long P=998244353; // Not necessarily this value.
const int n=3; // Not necessarily this value either.
long long seed=233; // And certainly not this value.
int gen()
{
    seed=seed*n%P;
    return seed%n;
}

Every time Alice returns a number $a$, Eve uses this pseudo-random number generator to generate a number $b$, and returns $a \oplus b$ (XOR, i.e., ^ in C++) to Bob.

You are Bob, and you have obtained $\texttt P$ and $\texttt n$ through some operations, but you do not know $\texttt{seed}$. You need to find $y$ within 100 queries.

Implementation Details

You do not need to, and should not, implement the main() function, nor should you read or write any information to standard input/output streams.

You only need to include the header guess.h and implement the following functions:

void init(int subtask_id,int T);
long long solve(long long P,int n);

• The init function will be called exactly once.
  • The parameter subtask_id indicates the current test case ID.
  • The parameter T indicates the number of test cases in the current test point.
• The solve function will be called $T$ times.
  • The parameters n and P are the parameters of Eve's pseudo-random generator.
  • You need to return Alice's number $y$.

You can call the following function:

int query(long long x);

• The parameter x represents the number Bob asks Alice.
• You must ensure $0 \le x \le 10^{18}$.
• The return value has been modified by Eve.

Sample Interactor

In the provided files, you can find the sample interactor grader.cpp. You can use the implementation of the interactor to help you understand and implement this problem. Note that during final testing, the implementation of the interactor will differ from the sample interactor, so you should not rely on the implementation of this interactor.

The sample interactor reads data from standard input in the following format:

• The first line contains two positive integers $\texttt{subtask_id}$ and $\texttt T$.
• The next $T$ lines each contain four integers $\texttt P, \texttt n, \texttt{seed}, y$, representing one test case.

During the interaction, if any error occurs, the interactor will output an error message and exit. Otherwise, the interactor will output the maximum number of queries at the end.

You can compile your program in the terminal using the following command:

g++ grader.cpp guess.cpp -o guess.exe -O2

Examples

Input 1

0 1
998244353 3 332748118 3

Output 1

3

Note

The following is a valid interaction process for the input above:

In this interaction process, the player program guessed the $\texttt{seed}$, so only the first return value needed to be XORed with 1.

Constraints

If you do not return the result within the time and memory limits for a test point, or if a runtime error occurs, or if the final returned answer is incorrect, your score for that test point will be 0.

Otherwise, let $Q$ be the number of times you called the query function in that test point, and $S$ be the full score for that test point, then:

• If $Q_\text{max} < Q$, your score is 0.
• If $Q_\text{min} < Q \leq Q_\text{max}$, your score is $S \cdot \left( 1 - 0.7 \cdot \dfrac{Q - Q_\text{min}}{Q_\text{max} - Q_\text{min}} \right)$.
• If $Q \leq Q_\text{min}$, your score is $S$.

In a subtask, your score is the minimum of the scores of all test points.

For all data, $10^3 \le P \le 10^{18}, 3 \le n \le 4, 0 \le \texttt{seed} < P, T \le 100, Q_{\min}=100, Q_\text{max}=200$. It is guaranteed that $P$ is a prime number.