Background

簡単なことも解らないわ
あたしって何だっけ
それすら夜の手に絆されて
愛のように 消える 消える
さようならも言えぬ儘泣いた フォニイ フォニイ フォニイ
嘘に絡まっているあたしはフォニイ
ANTIPATHY WORLD

Problem Description

This is an IO interactive problem.

There are $n$ flowers, and each flower has a positive integer beauty value.

She found that there exists a flower whose beauty value is at least twice the beauty value of any other flower.

You want to know which flower it is, so you may make at most $k$ queries. In each query, you give two positive integers $i, j \in [1, n]$, and Ke Bu will tell you the absolute value of the difference between the beauty values of the $i$-th and the $j$-th flowers.

You want to use the answers to these queries to determine which flower is the most beautiful.

Interaction Format

This problem has multiple test cases.

In the first line, the interactor provides an integer $T$, the number of test cases.

For each test case, the first line contains two positive integers $n, k$.

For each of your queries, output ? i j. The interactor will return a non-negative integer, representing the difference between the beauty values of the $i$-th and the $j$-th flowers.

If you have obtained the answer, output ! i to indicate that the $i$-th flower is the most beautiful. After that, you should start processing the next test case.

After each output, please flush the buffer.

You may use the following statements to flush the buffer:

• For C/C++: fflush(stdout)；
• For C++: std::cout << std::flush；
• For Java: System.out.flush()；
• For Python: stdout.flush()；
• For Pascal: flush(output)；
• For other languages, please refer to the corresponding documentation.

In particular, for C++, if you use std::endl instead of '\n' when printing a newline, it will also flush the buffer automatically.

Input Format

See "Interaction Format".

Output Format

See "Interaction Format".

1
3 114514

3

2

1

? 1 2

? 1 3

? 2 3

! 1

Hint

The sample shows one possible interaction, where the beauty values of the flowers are $\{4,1,2\}$.

This problem uses bundled testdata.

• Subtask 1 (20 points): $k=\dfrac{n(n-1)}{2}$, $n \le 200$.
• Subtask 2 (30 points): $k=n$.
• Subtask 3 (50 points): $k=\left\lfloor\dfrac{n}{2}\right\rfloor+2$.

For all testdata, let the beauty values of all flowers be $a_i$. $1 \le T \le 25$, $3 \le n \le 5 \times 10^4$, $1 \le a_i \le 10^8$.

Translated by ChatGPT 5