Interactive Piecewise Linear Function Query

This is an interactive IO problem.

You are given a linear function \(f(x)=kx+b\) defined for \(1\le x\le n-1\), where \(k,b\) are integers and \(k>0\). vectorwyx modifies this function by choosing an integer \(t\) (\(1\le t\le n-1\)) and shifting the part of the function on and to the right of the vertical line \(x=t\) by 1 unit to the right. He then connects the endpoints of the two pieces with a straight line to form a piecewise function \(g(x)\) defined as follows:

[ g(x)=\begin{cases} kx+b, & 1\le x<t,\[6pt] kt+b, & t\le x <t+1,\[6pt] k(x-1)+b, & t+1\le x\le n. \end{cases} ]

Your task is to determine the value of \(t\) by interacting with the judging system.

Interaction Protocol

1. First, an integer \(T\) is read from standard input, indicating the number of test cases.
2. For each test case, three integers \(n, Q, P\) are read from the input.
3. You can then make at most \(Q\) queries per test case by printing a query in the form: ? l r p, where \(1\le l\le r\le n\) and \(2\le p\le P\). After each query, flush the output buffer. The judge will respond as follows:
   • If the query range is invalid, the response will be \(-2\), and your program must exit immediately.
   • If \(g(l)=g(r)\), the response will be \(-1\).
   • Otherwise, the response will be \((g(l)+g(r)) \bmod p\).
4. Once you have deduced \(t\), print the answer in the form: ! t (and flush the output buffer). You are allowed only one final answer per test case, and it must be the last operation.
5. After printing the answer, the judge will output a feedback integer: \(1\) if your answer is correct for that test case, or \(0\) if it is incorrect. If \(0\) is received, your program must exit immediately.

Note: In the submitted solution below, to simulate the interactive process for offline testing, the hidden value \(t\) is provided as additional input after \(n, Q, P\). In a real interactive environment, you would deduce \(t\) using queries.

inputFormat

The input starts with an integer \(T\) representing the number of test cases. For each test case, a line containing three integers \(n, Q, P\) is given. For offline simulation purposes, an extra integer representing the hidden value \(t\) is provided immediately after.

Example:

3
5 10 100
3
10 20 50
7
8 15 10
4

outputFormat

For each test case, output the answer in the format ! t on its own line, where \(t\) is the hidden integer determined by the interactive queries.

sample

1
5 10 100
3

! 3