Interactive Random Number Generator Seed Recovery

This is an interactive problem.

Lloyd has a random number generator. For a given random seed \(s\) and generator type \(t\), the \(x\text{-th}\) (with \(x < p\)) random number produced is given by:

\[ r_{s,t}(x)=\begin{cases} s^x \bmod p &\quad t=1,\\[6pt] x^s \bmod p &\quad t=2,\end{cases} \]

where \(p\) is a fixed prime and \(0 \le s < p-1\). Before you start querying, the generator has already produced some random numbers; once you begin querying, no other random accesses occur (that is, the numbers you obtain form one continuous block). You can call the generator to get a random number. After several calls you must determine \(s\). It is guaranteed that a solution exists and that within 5 queries you can uniquely determine \(s\).

---

Implementation Details:

• The problem is interactive.
• The first line of input contains two positive integers \(t\) and \(p\).
• You can perform the following two operations with the interactive library:
  • ?: Call the random number generator once. After that, you can read one integer from the standard input as the generated number.
  • ! s: Report the discovered seed \(s\) and then immediately terminate your program.
• Remember to flush the output buffer after every operation.
• The scoring is explained in the data section. It is guaranteed that if you use no more than 19930 queries (which is enough for at least 1 point), the interactive library will run in less than 100ms.

Note: For generator type \(t=1\), observe that if you make two consecutive queries, then if the responses are \(r_1\) and \(r_2\) corresponding to indices \(x\) and \(x+1\), we have \(r_2 \equiv s \cdot r_1 \; (\bmod\; p)\) (with the convention that if \(r_1=0\) then \(s=0\)). For generator type \(t=2\), you may need more queries; one correct strategy is to query 5 times to obtain responses \(r_1, r_2, r_3, r_4, r_5\). Suppose the first query corresponds to index \(k+1\) (with an unknown offset \(k\)). Then we have:

\[ \begin{aligned} r_1 &\equiv (k+1)^s \; (\bmod\; p),\\ r_2 &\equiv (k+2)^s \; (\bmod\; p),\\ r_3 &\equiv (k+3)^s \; (\bmod\; p),\\ r_4 &\equiv (k+4)^s \; (\bmod\; p),\\ r_5 &\equiv (k+5)^s \; (\bmod\; p). \end{aligned} \]

You can then brute force the unique \(s\) (and the corresponding residue \(a=k+1\) modulo \(p\)) over \(1 \le a < p\) and \(0 \le s < p-1\). It is guaranteed that in 5 queries you will have enough information to uniquely determine \(s\).

inputFormat

The first line contains two integers \(t\) and \(p\). After that, whenever you output a query (a line containing ?), you will receive an integer from the standard input which is the generator's response.

outputFormat

When you have determined the seed, output a line in the format ! s (without quotes) and terminate your program.

sample

1 17
15
11

! 3

</p>