Description

This is an interactive I/O problem.

You have a linear function $f(x)=kx+b$ ($1\le x \le n-1$). This linear function satisfies that $k$ and $b$ are both integers and $k>0$.

vectorwyx modified this function. Specifically, he chooses an integer $t$ ($1\le t \le n-1$), shifts the part of the function on the line $x=t$ and to its right by $1$ unit to the right, and then connects the endpoints of the two parts with a line segment, obtaining a piecewise function $g(x)$:

$$g(x)=\begin{cases} kx+b&1\le x<t\\ kt+b& t\le x <t+1\\ k(x-1)+b& t+1\le x \le n \end{cases}$$

Please obtain the value of $t$ through interaction.

Interaction

There are multiple test cases in one test point.

1. First read an integer $T$ from standard input, representing the number of test cases.
2. Next, you will interact for $T$ test cases. For each test case, first read three integers $n,Q,P$ from standard input.
3. You can make a query by outputting ? l r p ($1\le l \le r \le n$, $2\le p \le P$) to standard output. In one test case, you can perform at most $Q$ ? operations. The interactor will process your query in the following order and send the result to standard input:
   • If your query range is invalid, the answer is $-2$. The interactor will immediately return WA. You must exit your program immediately to avoid TLE caused by interacting with an already terminated interactor.
   • If $g(l)=g(r)$, the answer is $-1$.
   • Otherwise, the answer is $(g(l) + g(r))\bmod p$.
4. You can output ! t to standard output to give the answer. You can answer only once, and the answer operation must be the last operation you perform in each test case. After the interaction ends, read an integer $x$ (0 or 1) from standard input. If $x=1$, your answer for the current test case is correct, and you should go back to step $2$ to proceed to the next test case. Otherwise, if $x=0$, you must exit your program immediately.

Do not forget to flush the output buffer after each output, otherwise you will get TLE.

Below are some ways to flush the output buffer in different languages:

• C++: fflush(stdout) or cout.flush().
• C: fflush(stdout).
• Java: System.out.flush().
• Python: stdout.flush().
• Pascal: flush(output).
• Other languages: please refer to the documentation of the corresponding language.

Input Format

See “Interaction”.

Output Format

See “Interaction”.

1
5 999 999

0

1

1

? 1 3 2

? 4 5 2

! 3

Hint

Sample Explanation

Note that the sample is only used to show the interaction rules, and it may not be logically meaningful.

Sample #1

$f(x)=3x-2$ ($1\le x \le 4$), $t=3$.

$$g(x)=\begin{cases} 3x-2&1\le x<3\\ 7& 3\le x <4\\ 3x-5& 4\le x \le 5. \end{cases}$$

So the result of the first query is $(g(1) + g(3))\bmod 2 = (1+7)\bmod 2=0$, and the result of the second query is $(g(4)+g(5))\bmod 2 = (7+ 10)\bmod 2=1$.

Constraints

This problem uses bundled judging. Also, there is no restriction that one subtask contains all other subtasks.

Subtask	Score	$n$	$Q=$	$P=$	$g(x)\le$	Special Property
$1$	$10$	$\le 10^9$	$42$	$2\times 10^{18}$	$10^{18}$	None
$2$	$20$		$30$	$2$		Slope $k$ is odd
$3$	$30$		$42$	$50$		None
$4$	$39$		$32$
$5$	$1$	$= 1162261531$			$7857125847061472735$

For $100\%$ of the data, it is guaranteed that $1 \le T \le 10$, $2\le n\le 1162261531$. Also, $\forall x \in [1,n], 0 \le g(x)\le 7857125847061472735$.

Notes

Since there is no restriction that one subtask contains all other subtasks, the upper bounds of $n$ and $g(x)$ in the “For $100\%$ of the data” part have no real meaning. However, if we directly wrote “For $100\%$ of the data, $n \ge 2$, $g(x)\ge 0$”, some reviewers might reject it as “Is this what you call constraints?”. Therefore, this meaningless upper bound is kept in this problem statement.

Translated by ChatGPT 5