M. Mine
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

Interaction

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:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;

Note that the interactor is not adaptive, which means that the hidden arrays do not depend on the queries you make.

Example
Input
2
7 6

1

0

10 10

1
Output
? 3 1 1 3 3

? 2 5 1 5 6

! 2 3

? 2 1 5 8 9

! 4 9
Note

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

  1. The first query is the red rectangle. As there is $$$1$$$ mine and $$$k$$$ is $$$3$$$, $$$1 \;\text{mod}\; 3 = 1.$$$ The detector returns $$$1$$$.
  2. The second query is the blue rectangle. As there are $$$2$$$ mines and $$$k$$$ is $$$2$$$, $$$2 \;\text{mod}\; 2 = 0$$$. The detector returns $$$0$$$.
  3. The program then reports that there is one mine at $$$(2, 3)$$$ which is correct and the program terminates.

In the second testcase, the field has $$$10$$$ rows and $$$10$$$ columns. Suppose there is only one mine located in $$$(4, 9)$$$.

  1. The only query for the mine that stays within row $$$1-8$$$ and column $$$5-9$$$ with $$$k = 2$$$. The detector returns $$$1$$$ as it detects the only mine in the field.
  2. The program then reports that there is one mine at $$$(4,9)$$$ which is correct and the program terminates.