This is an interactive problem.
Qatada and Dabbour have very strange habits. Sometimes they race through airport terminals, and sometimes they start screaming "Dorraya sin el dahab ya dorraya!" while trying to sell corn they do not even own.
Mukhtar says this is only the beginning.
One day, they sit on moving travelators, and then they lie down on them. Mukhtar finally had enough of their chaos.
To keep track of their madness, Mukhtar records a Chaos Score (a unique integer) every time something unusual happens. He stores these values in two separate files one for Qatada and one for Dabbour. Each file contains $$$n$$$ distinct integers in range $$$[1, 2 \cdot 10^9]$$$, and both files are sorted in strictly decreasing order.
One day, Mukhtar's system crashes. The screen freezes, and the full files are no longer accessible. The only remaining functionality is a restricted query system, which you may ask at most $$$72$$$ queries in total.
The interaction begins by reading two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2n$$$).
You may ask queries in the following format:
where $$$1 \le i \le n$$$.
Finally, you must output:
After printing the answer, your program must terminate.
Each output must be flushed immediately.
It can be proven that the answer can always be determined within the allowed number of queries.
4 3 ? 1 1 10 ? 2 1 9 ? 1 2 7 ? 2 2 5
! 7
Explanation of first test case the first array was $$$a = [10, 7, 4, 2]$$$ and the second array $$$b = [9, 5, 3, 1]$$$ we need to find the $$$3^{rd}$$$ largest value among all elements from both arrays combined.
After conceptually merging the two arrays $$$a + b = [10, 9, 7, 5, 4, 3, 2, 1]$$$ the $$$3^{rd}$$$ largest value is $$$7$$$.
The interaction shown in the sample demonstrates one possible sequence of queries used to determine the answer.
| ASU Coding Cup 11 |
|---|
| Закончено |
