Background

The team members are all thinking about organizing the anniversary celebration, but Xiaoxi just wants to slack off.

So Xiaoxi took out their favorite sequence to test you.

Problem Description

Xiaoxi has a shuffled arithmetic progression $A$.

You can make two types of queries:

1. Ask for the order relationship (in the arithmetic progression, in the non-mod sense) between the numbers at indices $x, y$ in the original sequence.
2. Ask for the value (in the arithmetic progression, in the mod sense) of the number at index $x$ in the original sequence.

However, due to a problem with the interactive library, query type 2 can be used at most $q$ times.

Given the length $n$ of the arithmetic progression, the query limit $q$, and the fixed modulus $p=10^{9}+7$, find the common difference $d$ of this arithmetic progression.

The total number of queries must not exceed $2n$. After finishing the interaction, output the answer immediately.

Interaction:

Input the sequence length $n$ and the query limit $q$ to start the interaction.

During the interaction, you may perform the two types of queries described above.

For the first type of query, the interactive library returns $1$ meaning $>$ or $0$ meaning $<$. The query format is > x y.

For the second type of query, the interactive library returns a positive integer $A_i$. The query format is ? x.

After you determine the answer, output one line in the form ! d and stop the interaction.

After outputting a line, flush the buffer:

In C++, use fflush(stdout) or cout.flush().

In Pascal, use flush(output).

In Python, use stdout.flush().

For other languages, please check the documentation yourself.

Please follow the statement to complete the interaction. Making invalid queries may cause issues such as TLE or WA.

Input Format

See Interaction.

Output Format

See Interaction.

The testdata guarantees that there will not be multiple possible values of $d$.

3 6
1
2
3

? 1
? 2
? 3
! 1

Hint

For $50\%$ of the testdata, it is guaranteed that $q=2n$.

For the other $50\%$ of the testdata, it is guaranteed that $q=2$.

For $100\%$ of the testdata, it is guaranteed that $2\leq n\leq 100000$, $0\leq A_i< p$, $1\le d < p$.

Translated by ChatGPT 5