Nobita was tired of getting bullied by Gian. As he is a cultured citizen, he chose to solve this problem by planting $$$N$$$ mines in the school, which is a rectangular field of $$$R$$$ rows and $$$C$$$ columns. After he finished his business, he went back to his house and told Doraemon what he did. Doraemon was so proud of him, then asked if Nobita remembered where he put the mines. Unsurprisingly, he couldn't recall the location of any mine, and not even the number of mines he put in. Doraemon, however, expected this; he prepared a device that can locate every mine on the field. But the device requires the location of any mine in that field first.
Nobita was given a detector that receives a rectangular area and a positive integer $$$k$$$ that must be no greater than $$$20$$$. The detector will return the number of mines in that specified area modulo $$$k$$$.
Since Nobita needs to finish this fast for some reason, he can use this device not so many times before it is too late.
Your task is to help Nobita locate any mine (one mine) in the field using the detector no more than $$$69$$$ times.
Each test contains multiple test cases. The first line contains the number of test cases t ($$$1 \leq t \leq 100$$$).
For each test case, the first line contains 2 integers $$$R$$$, $$$C$$$ ($$$1 \leq R, C \leq 10^{9}$$$) — the number of rows and columns of the field.
The number of mines (i.e. $$$N$$$) in each test case is at least $$$1$$$ and at most $$$10^6$$$. Note that the number of mines is not provided.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^6$$$.
To use the detector, you should print a new line in the following format: "? $$$k$$$ $$$r_1$$$ $$$c_1$$$ $$$r_2$$$ $$$c_2$$$" ($$$1 \leq k \leq 20, 1 \leq r_1 \leq r_2 \leq R, 1 \leq c_1 \leq c_2 \leq C$$$).
As a response, the detector will return the amount of mines which are located at row $$$i$$$ column $$$j$$$ in that rectangle ($$$r_1 \leq i \leq r_2$$$, $$$c_1 \leq j \leq c_2$$$) modulo $$$k$$$.
To report the answer, you should print a new line in the following format: "! $$$r$$$ $$$c$$$" indicating that there is a mine located at row $$$r$$$ column $$$c$$$.
If you use the detector more than $$$69$$$ times, you ask a malformed query, or your answer is wrong, you will get Wrong answer.
After printing a query, do not forget to output the end of line and flush the output. To do this, use:
Note that the interactor is not adaptive, which means that the hidden arrays do not depend on the queries you make.
2 7 6 1 0 10 10 1
? 3 1 1 3 3 ? 2 5 1 5 6 ! 2 3 ? 2 1 5 8 9 ! 4 9
In the first testcase, the field has 7 rows and 6 columns. Suppose that the mines are located in $$$(2, 3), (5, 3), (5, 6)$$$.
In the second testcase, the field has $$$10$$$ rows and $$$10$$$ columns. Suppose there is only one mine located in $$$(4, 9)$$$.