Background

Upd on 2024/10/22 Added one set of hack testdata (#13).

Problem Description

This is an interactive problem.

Lloyd has a random number generator. For a random seed $s$ and generator type $t$, the random number it generates at the $x$-th time ($x<p$) is:

$$r_{s,t}(x)=\begin{cases}s^x\bmod p&t=1\\x^s\bmod p&t=2\end{cases}$$

where $p$ is a fixed prime number. $0\le s<p-1$.

Now you are given $p,t$. It is known that the random number generator has already generated some random numbers before you start querying, and while you are generating random numbers, there will be no other access to the random number generator (that is, you will get a consecutive segment of random numbers). Each time, you can call the generator to get one random number, and after several calls, find the value of the seed $s$. It is guaranteed that a solution exists, and after 5 queries you will definitely get a unique solution.

---

Implementation details

This problem uses interactive IO.

The first line contains two positive integers $t,p$.

After that, you can send the following two types of operations to the interactive library:

• ?, meaning to call the random number generator once; then you can read the value generated by the generator from standard input.
• ! s, report the $s$ you have found.

After sending the ! operation, you should terminate the program immediately. Also, you need to flush the buffer after each operation. The scoring method is described in the Constraints section.

If your operations do not follow the interactive format, unpredictable results may occur. It is guaranteed that when the number of interactions does not exceed 19930 (that is, you can get at least 1 point), the interactive library runtime will not exceed 100ms. For more than 19930 interactions, the runtime is not guaranteed.

Input Format

See the implementation details part in the description.

Output Format

See the implementation details part in the description.

1 10007

4960

?

! 114

2 10007

4960

6980

?

?

! 514

Hint

Sample explanation

The samples are for reference only and may not have actual logic.

Sample 1: $p=10007$, $s=114$, and it had generated random numbers $513$ times before the queries.

Sample 2: $p=10007$, $s=514$, and it had generated random numbers $113$ times before the queries.

---

Constraints

This problem uses bundled tests. (The Subtask score is the minimum score among all test points within the Subtask.)

• Subtask 1 (20pts): $t=1$.
• Subtask 2 (20pts): $p\le 10^3$.
• Subtask 3 (60pts): No special constraints.

For all testdata, $2\le p\le2\times10^6$ and $p$ is prime, $t\in\{1,2\}$. A solution is guaranteed to exist.

For each test point, if you send ? to the interactive library $c$ times, then the score you can get is given by:

$$\mathrm{score}=\begin{cases}100&c\le 5\\\max\{0,100-\lceil10\ln(c)\rceil\}&\text{otherwise.}\end{cases}$$

Translated by ChatGPT 5