This is the Hard version of the problem. The difference between the versions is that in this version, you can make at most $$$30$$$ queries. You can hack only if you solved all versions of this problem.

This problem is interactive.

There is a permutation$$$^{\text{∗}}$$$ $$$p$$$ of the integers from $$$0$$$ to $$$n-1$$$ hidden from you. Additionally, you are given $$$q$$$ ranges $$$[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$$$ where $$$1 \le l_i \le r_i \le n$$$.

You need to discover the maximum $$$\operatorname{MEX}$$$ among the values of $$$p$$$ in the $$$q$$$ ranges that are given to you in the input. Formally, you must discover the value of $$$\max _{i=1}^q {\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$$$$$$^{\text{†}}$$$. To do this, you may make at most $$$30$$$ queries of the following form:

Choose any two integers $$$1 \le l \le r \le n$$$ and you will receive the value $$$\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$$$.

$$$^{\text{∗}}$$$A permutation of the integers from $$$0$$$ to $$$n-1$$$ is a sequence of $$$n$$$ elements where every integer from $$$0$$$ to $$$n-1$$$ appears exactly once. For example, the sequence $$$[0, 3, 1, 2]$$$ is a permutation, but the sequence $$$[0, 0, 2, 1]$$$ is not.

$$$^{\text{†}}$$$The $$$\operatorname{MEX}$$$ of a sequence is defined as the smallest non-negative integer that does not appear in that sequence. For example, $$$\operatorname{MEX}([0, 0, 1, 3]) = 2$$$ and $$$\operatorname{MEX}([1, 2, 2]) = 0.$$$

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains exactly two integers $$$n$$$ and $$$q$$$ ($$$4 \le n \le 10^4$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — the size of the permutation and the number of ranges, respectively.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ do not exceed $$$10^4$$$ and $$$3 \cdot 10^5$$$ respectively over all test cases.

Additional Constraint: it is guaranteed that no range is repeated in the same test case.

Interaction

To ask a query, output a line in the following format (without the quotes):

"? $$$l$$$ $$$r$$$" ($$$1 \le l \le r \le n$$$)

The jury will return a single integer, the value of $$$\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$$$.

When you have found the answer, output a single line in the following format:

"! $$$x$$$" ($$$0 \le x \le n$$$).

After that, proceed to process the next test case or terminate the program if it was the last test case. Printing the answer does not count as a query.

The interactor is not adaptive, meaning that the values of the permutation are known before the participant asks the queries.

If your program makes more than $$$30$$$ queries, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you may get the Idleness Limit Exceeded verdict. To do this, use:

fflush(stdout) or cout.flush() in C++
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see the documentation for other languages.

Hacks

For hacks, use the following format.

The first line of the input should contain a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case should contain exactly two integers $$$n$$$ and $$$q$$$ ($$$4 \le n \le 10^4$$$, $$$1 \le q \le 3\cdot 10^5$$$) — the size of the permutation and the number of ranges you are given, respectively.

The second line should contain $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ — where $$$p_i$$$ is the $$$i$$$-th element of the permutation. It should hold that $$$p$$$ is a permutation containing integers $$$0$$$ to $$$n-1$$$.

The $$$i$$$-th of the next $$$q$$$ lines should contain two integers $$$l_i$$$, $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

It should hold that the sum of $$$n$$$ and $$$q$$$ do not exceed $$$10^4$$$ and $$$3 \cdot 10^5$$$ respectively over all test cases.

Additional Constraint: no range should be repeated in the same test case.

Note

In the first example, the hidden permutation is $$$p = [0, 3, 1, 2]$$$ and the ranges are $$$[1, 2], [2, 4], [1, 3]$$$. The third range is optimal, as $$$\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$$$, which is maximum.

In our first query, we ask about $$$l = 1, r = 3$$$ and the judge gives us the value $$$\operatorname{MEX}([p_1, p_2, p_3]) = 2$$$. In the second query, we ask about $$$l = 4, r = 4$$$ and the judge gives us the value $$$\operatorname{MEX}([p_4]) = 0$$$. Likewise, $$$\operatorname{MEX}([p_1]) = 1$$$ and $$$\operatorname{MEX}([p_1, p_2, p_3, p_4]) = 4$$$.

Somehow, we figure out that the answer we are looking for is $$$2$$$.

In the second example, $$$p = [3, 5, 0, 1, 4, 2]$$$.

In the third example, $$$p = [0, 1, 2, 3]$$$.

Note that this is just an explanation of the way the interaction works and does not show any strategy to solve the problem.

Diadrash (Hard Version)

Examples