F. Custom-Made Clothes
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

"Oh, poor Opalescence," I sighed as I watched Fluttershies surround the white Persian cat.

Rarity is always so busy, and honestly, she probably struggles to solve my problems. She is not really adept at this kind of magic.

While she was busy making customized clothing, she even turned around and gave me a problem. Her problem can be abstracted as follows:

There is an $$$n \times n$$$ matrix of positive integers $$$a_{i,j}$$$ ($$$1 \leq a_{i,j} \leq n \times n$$$), which satisfies that for each $$$i \gt 1$$$, $$$a_{i,j} \geq a_{i-1,j}$$$; and for each $$$j \gt 1$$$, $$$a_{i,j} \geq a_{i,j-1}$$$.

You're provided with only the size $$$n$$$ of the matrix, without knowledge of its element values $$$a_{i,j}$$$. However, you can inquire whether a given position $$$a_{i,j}$$$ in the matrix is not greater than a specified integer $$$x$$$.

You need to find the $$$k$$$-th largest value in $$${a_{i,j}}$$$ using no more than $$$50000$$$ queries.

Note that $$$a_{i,j}$$$ may have identical values. The $$$k$$$-th largest value is defined as the value of the $$$k$$$-th element when sorting the $$$n \times n$$$ elements in descending order.

Interaction

First, read the parameters $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq k \leq n \times n$$$) from the standard input.

Then, you can make no more than $$$50000$$$ queries. To make a query, output "? i j x"$$$\ $$$($$$1 \leq i,j \leq n$$$, $$$1 \leq x \leq n \times n$$$) on a separate line, and you should read the response from standard input. If $$$a_{i,j}\le x$$$, the standard input will return $$$1$$$, otherwise $$$0$$$.

Finally, to give your answer, output "! x"$$$\ $$$on a separate line, representing the $$$k$$$-th largest value in the matrix. The output of the answer is not counted towards the limit of $$$50000$$$ queries. After that, your program should terminate.

After outputting a query, do not forget to output end of line and flush the output. To do this:

  • fflush(stdout) or cout.flush() for C++;
  • System.out.flush() for Java;
  • stdout.flush() for Python;

It is guaranteed that the matrix remains unchanged during the interaction.

Example
Input
2 3

1

1

0

0

0
Output
? 1 1 2

? 1 2 2

? 2 1 2

? 2 2 2

? 1 2 1

! 2
Note

One possible matrix in the example is $$$\begin{bmatrix}1 & 2 \\ 3 & 4 \end{bmatrix}$$$.