E. Broken Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You, a wizard whose creation was destroyed by a dragon, are determined to hunt it down with a magical AOE tracker. But it seems to be toyed with...

This is an interactive problem.

There is a hidden binary array $$$a$$$ of length $$$n$$$ ($$$\mathbf{n}$$$ is a power of 2) and a hidden integer $$$k\ (2 \le k \le n - 1)$$$. The array $$$a$$$ contains exactly one 1 (and all other elements are 0). For two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), define the range sum $$$s(l, r) = a_l + a_{l+1} + \cdots + a_r$$$.

You have a magical device that takes ranges and returns range sums, but it returns the opposite result when the range has length at least $$$k$$$. Formally, in one query, you can give it a pair of integers $$$[l, r]$$$ where $$$1 \le l \le r \le n$$$, and it will return either $$$0$$$ or $$$1$$$ according to the following rules:

  • If $$$r - l + 1 < k$$$, it will return $$$s(l, r)$$$.
  • If $$$r - l + 1 \ge k$$$, it will return $$$1 - s(l, r)$$$.

Find $$$k$$$ using at most $$$33$$$ queries.

The device is not adaptive. It means that the hidden $$$a$$$ and $$$k$$$ are fixed before the interaction and will not change during the interaction.

Interaction

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

The first line of each test case contains one positive integer $$$n$$$ ($$$4 \le n \le 2^{30}$$$) — the length of the hidden array. It is guaranteed that $$$\mathbf{n}$$$ is a power of 2; that is, $$$n = 2^m$$$ for some non-negative integer $$$m$$$.

You can make queries in the following way — print one line of the form "$$$\mathtt{?}\,l\,r$$$" where $$$1 \le l \le r \le n$$$. After that, read a single integer: $$$0$$$ or $$$1$$$, as described in the statement.

If you want to print the answer $$$k$$$, output "$$$\mathtt{!}\,k$$$". Then, the interaction continues with the next test case.

Printing the answer does not count towards the number of queries made.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

The format of the hacks should be the following: the first line should contain one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases should follow.

The first and only line of each test case should contain three integers $$$n$$$, $$$p$$$, and $$$k$$$ ($$$4 \le n \le 2^{30}$$$, $$$1 \le p \le n$$$, $$$2 \le k \le n - 1$$$) — the length of the hidden array $$$a$$$, the position of the only 1 in $$$a$$$, and the hidden $$$k$$$. $$$n$$$ must be a power of $$$2$$$.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2
8

0

0

1

0

4

1

0
Output
? 3 5

? 1 8

? 4 8

? 3 8

! 6

? 3 3

? 3 4

! 2
Note

In the first test case, $$$k = 6$$$ and the 1 in the hidden array is at index 6, so $$$a = [0, 0, 0, 0, 0, 1, 0, 0]$$$.

  • For the query 3 5, since $$$5-3+1 = 3 < k$$$, the device answers correctly. Since 6 is not contained in the range $$$[3, 5]$$$, the device answers $$$0$$$.
  • For the query 1 8, since $$$8 - 1 + 1 = 8 \ge k$$$, the device answers $$$0$$$ incorrectly.
  • For the query 4 8, since $$$8 - 4 + 1 = 5 < k$$$, the device answers $$$1$$$ correctly.
  • For the query 3 8, since $$$8 - 3 + 1 = 6 \ge k$$$, the device answers $$$0$$$ incorrectly.
The example solution then outputs $$$6$$$ as the answer, which is correct.

In the second test case, $$$k = 2$$$ and the 1 in the hidden array is at index 3, so $$$a = [0, 0, 1, 0]$$$.

Note that the example solution may not have enough information to determine $$$k$$$ above; this is only an example.