P7849 "JZOI-2" Guess the Sequence

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.

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 $ 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.**

See Interaction.

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

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