This is an interactive problem.

Given a sequence $a$ of length $n$, where all elements in $a$ are distinct, a sequence $b$ of length $n$ is constructed such that $b_i = a_i \oplus x$, where $x$ is a non-negative integer satisfying $0 \le x < 2^{30}$. You know the sequence $a$ but do not know $x$ or the sequence $b$. You wish to determine the total ordering of all elements in $b$ through a series of queries.

In each query, you need to provide an index $1 \le p \le n$. The interactor will return the index of the element $b_i$ that is the smallest among all $b_i > b_p$. Formally, let $res = \min_{1 \le i \le n, b_i > b_p} b_i$. The interactor will return the unique index $i$ such that $b_i = res$. If no $b_i > b_p$ exists, the interactor will return $-1$.

To reduce the output, you only need to output the smallest non-negative integer $x_0$ such that the sequence $c$ of length $n$ constructed by $x_0$, where $c_i = a_i \oplus x_0$, has the same total ordering as $b$. In other words, $c$ should satisfy $\forall 1 \le i < j \le n, (b_i - b_j)(c_i - c_j) > 0$.

In each round of interaction, you can perform at most 30 queries. For each test case, you need to perform $m$ rounds of interaction. The values of $n$ and $a$ are the same across different rounds, but $x$ and the sequence $b$ may differ.

Interaction

First, read two positive integers $n, m$ ($1 \le n \le 4 \times 10^5, 1 \le m \le 3 \times 10^3$), representing the sequence length and the number of interaction rounds.

Next, read $n$ non-negative integers representing the sequence $a$ ($0 \le a_i < 2^{30}$).

Then, perform $m$ rounds of interaction. The format for each round is as follows:

• First, you can perform at most 30 queries. The format for each query is ? p. The interactor will return an integer $q$. If $q = -2$, it means you have exceeded the query limit or performed an illegal operation; you must exit immediately, and the judge will return a Wrong Answer. If $q = -1$ or $1 \le q \le n$, the interactor has responded to your query normally.
• Once you have determined $x_0$, you can submit the result in the format ! x0. Regardless of whether the result is correct, the current round of interaction will end, and you will proceed to the next round (or finish if it is the last round). Submitting the answer does not count towards the query limit.

Note that during the $m$ rounds of interaction and after outputting the answer, you must flush the buffer after each output. This can be achieved in various languages as follows:

• For C/C++, use fflush(stdout) or cout.flush().
• For Java, use System.out.flush().
• For Python, use stdout.flush().

During the interaction, you must ensure that the $p$ provided in your queries satisfies $1 \le p \le n$, and the $x_0$ submitted satisfies $0 \le x_0 < 2^{30}$, otherwise unpredictable errors may occur.

Examples

Input 1

5 1
1 2 3 4 5

Output 1

? 1
? 2
? 3
? 4
? 5
! 3

Note

It is clear that this determines $b_4 > b_5 > b_1 > b_2 > b_3$. We can find that $x_0 = 3$ is the smallest $x_0$ that satisfies this total ordering, so the final answer should be 3.

In fact, the actual $x$ might not be 3; for example, one can find that the sequence $b$ generated by $x = 11$ also satisfies this total ordering, but this is not important because we are not required to recover $x$.