Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hououin Kyouma!

By shefin · Limits 3s, 512 MB · Interactive

Okabe Rintarou, the mad scientist is doing research to find the most desired Steins Gate. Besides being a mad scientist, he is a student too. As a result, he has to attend online classes. Class $i$ occurs between $B_{i}$th hour and $E_{i}$th hour ($B_i \leq E_i$). That is to say, Class $i$ begins at $B_i$th hour and ends at $E_i$th hour. [N.B: $B_i$th hour and $E_i$th hour are considered as class hours too.]

To continue research, Okabe needs a lot of free hours. The hours when there are no classes are free hours. As Okabe likes to work continuously without any break, he wants to determine the maximum number of consecutive free hours he can get between $1$st hour and $T$th hour (inclusive).

For example: Suppose, there are $3$ online classes and $T = 11$. Class $1$ occurs between $[1, 3]$ hours, class $2$ occurs between $[4, 5]$ hours and class $3$ occurs between $[ 9, 9]$ hour. So, the free hours are $\{6, 7, 8, 10, 11\}$. Among them, the maximum number of consecutive free hours is $3$ and they are hours $\{6, 7, 8\}$.

But there’s a problem. Due to an organization’s conspiracy, Okabe can only ask the amount of free hours between $[t_1, t_2]$ hour to the class scheduling system where $1 \leq t_1 \leq t_2 \leq T$. He finds out that he needs to ask a lot of questions to the system to determine what he wants to know. So, he commands you to help him as a “Super Hacker” friend.

Input

At first, there will be a line containing an integer $C$, the number of test cases.

In each test case, the first line will contain the number of classes $N$ and the value of the integer $T$ separated by a single space.

In each test case, to ask a question, print ”? i j” (without quotes) in a line, where $1 \leq i \leq j \leq T$. Then, you should read a single integer. The integer will denote the total free hours between $[i, j]$ hours (inclusive).

If you think you’ve determined the maximum number of consecutive free hours, print ”! x” (without quotes) in a line where $x$ denotes the maximum number of consecutive free hours.

After that you’ve to read a line containing an integer $V$. If your answer is correct, you’ll receive $V=1$ and you’ve to proceed for the next test case or terminate your program if it’s the last test case. If your answer is wrong, you’ll receive $V=-1$ and you’ve to terminate your program.

You can ask at most $Q$ questions (excluding printing answer) in each test case. If you exceed the number of questions or ask any invalid question, you will receive $-1$ as the answer of your question.

At any point, terminate your program immediately after receiving $−1$ and you will see “Wrong Answer” verdict. Otherwise, you can get an arbitrary verdict (except “Accepted”) because your solution will continue to read from a closed stream.

Since this is an interactive problem, don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf or cout.flush() for cout in C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult its documentation.

Scoring

Subtask 1 (10 Points):
$1 \leq C \leq 8$
$1 \leq N \leq 300$
$N \leq T \leq 10^{4}$
$Q = 10^4$

Subtask 2 (55 Points):
$1 \leq C \leq 8$
$1 \leq N \leq 500$
$N \leq T \leq 10^{15}$
$Q = 5\times10^4$

Subtask 3 (35 Points):
$1 \leq C \leq 8$
$1 \leq N \leq 500$
$N \leq T \leq 10^{15}$
$Q = 4.3\times10^4$

You may assume that the beginning and the ending hour of all classes lies between$[1, T]$ hour (inclusive) and there are no collisions in the class schedule.

Output

Let, the number of test case, $C=1$. A sample interaction based on the example given in problem statement may look like:

> 1
> 3 11
< ? 2 9
> 3
< ? 6 11
> 5
< ? 1 11
> 5
< ? 7 7
> 1
< ! 3
> 1

> indicates what your program reads and < indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.

The interval of the $1^{st}$ question is hours $[2,9]$. Total free hours among them is $3$ (hour $\{6,7,8\}$).
The interval of the $2^{nd}$ question is hours $[6,11]$. Total free hours among them is $5$ (hour $\{6,7,8,10,11\}$).
The interval of the $3^{rd}$ question is hours $[1,11]$. Total free hours among them is $5$ (hour $\{6,7,8,10,11\}$).
The interval of the $4^{th}$ question is hour $[7,7]$. Total free hours among them is $1$ (hour $\{7\}$).

Discussion

Statistics


0% Solution Ratio

Submit

Login to submit

Editorial

Subtask 1: Always $ Q&gt; = T $ here. So by asking $ T $ questions, it can be found out which hour...