Background

Problem Description

Please note the differences between this problem and P15425 Nobody Tells — 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{<M}$, and the judge tells you the value of $f_i$.

Your task is to guess the value of $(p, q)$ after at most $3$ queries. In particular, you may guess two pairs of $(p, q)$ at the same time, see the interaction details.

Interaction Details

This problem contains multiple test cases.

In the first line of the input, the judge will give your program an integer $T$, meaning the number of test cases in this test point.

For each test case:

The judge will have the $(p, q)$ for this test case. This also means the judge is non-adaptive.

In the first line, the judge inputs two integers $M, L$ to your program, meaning the modulus and the query restriction.

For each query, you need to output ? i, meaning querying the value of $f_i$.

Under normal conditions, the judge will input an integer in $[0, M)$, which is the $f_i$ you queried.

If any of the following happens, the judge will immediately terminate the interaction and force your program to exit, and this test point will be judged as failed:

• The number of queries exceeds $3$.
• $i$ is not in the range $L\le i<M$.

After you have guessed the possible $(p, q)$, you need to output ! p1 q1 p2 q2, meaning the two pairs of $(p, q)$ you guess are $(p_1, q_1)$ and $(p_2, q_2)$. This operation does not count toward the $3$ queries. In particular, you must ensure that all four numbers are in the range $[1, M)$, otherwise the judge will immediately terminate the interaction and force your program to exit, and this test point will be judged as failed.

If at least one of the two answer pairs matches the value held by the judge, then this test case is passed; otherwise it is failed, and the judge will immediately terminate the interaction and force your program to exit.

If you pass all test cases in a test point, then this test point will be judged as passed.

1
5 1

3

1

? 1

? 2

! 3 2 1 1

Hint

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

Subtask	Special Property	Score
1	$L=1$	$2$
2	$T\le 500$ and $L=15$	$10$
3	$M=10^6+3$	$20$
4	$T\le 10$ and $M\le 5\times 10^6$
5	None	$48$

Afterword

:::epigraph[——《Nobody Tells》] The lights that guide the way along the journey
You are one of them :::

Translated by ChatGPT 5