P15427 Nobody Tells (Original Version)


**Please note the differences between this problem and [P15425 Nobody Tells](https://www.luogu.com.cn/problem/P15425) — this problem has stricter constraints on queries.** ---------- **This is an interactive problem.** Coola has two numbers $p, q$, and a prime number $M$. We generate a sequence $\{f_i\}$ in the following way: $$ \begin{cases} f_{0}=1\\ f_{1}=p\\ f_{i}=(pf_{i-1}+qf_{i-2})\bmod M,&i>1 \end{cases} $$ The interactive judge will give you $M$ and a parameter $L$. You can query the judge at most $3$ times: - Provide an index $L\le i\red{

N/A

N/A

### Explanation of Sample #1 The data held by the judge is $p=3, q=2, M=5, L=1$. In the first interaction, your program queries the value of $f_1$ with $\texttt{? 1}$. Clearly $f_1=p=3$, so the judge inputs $3$ to your program. In the second interaction, your program queries the value of $f_2$ with $\texttt{? 2}$. We have $f_2=(pf_1+qf_0)\bmod 5=11\bmod 5=1$. Therefore the judge inputs $1$ to your program. Since $f_2=(p^2+q)\bmod 5$, and we know $p=3$, we can solve $q=2$. So you have determined the answer using two queries, and you can output $\texttt{! 3 2 1 1}$. Since the first pair of answers is correct, the second pair does not matter, so $\texttt{! 3 2 4 3}$ is also a valid output. However, $\texttt{! 3 2 1 5}$ or $\texttt{! 3 2 0 4}$ are not, because you must ensure all four numbers are in the range $[1, 5)$. ### Constraints **This problem uses bundled tests.** For $100\%$ of the data, $1\le T\le 10^5$. $10^6\le M\le 10^9$, and $M$ is guaranteed to be **prime**. $0\le L\le 5\times 10^5$. The judge is **non-adaptive**, and $1\le p, q