P9219 "TAOI-1" Antipathy World

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

**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

See "Interaction Format".

See "Interaction Format".

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