Description

Dream divides all of Tommy's music discs into $n$ categories. In the $i$-th category, there are $2^m - 1$ music discs. Each disc has a unique positive integer importance value.
Now Dream has sorted the discs within each category in increasing order of importance. Dream wants to know which disc has the $k$-th smallest importance among all discs.

Because there are too many music discs, Dream cannot directly give you the importance of every disc. While searching for the answer, Dream allows you to query the importance value of the disc that is the $j$-th smallest in the $i$-th category.

Input Format

At the beginning of the interaction, the judge inputs four positive integers $n$, $m$, $k$, and $Th$ on the first line, where $Th$ is the maximum number of queries allowed.
For each query, the judge will reply with the importance value of the disc at the queried position.

Output Format

Your program can perform two operations:

1. ? i j, which queries the importance of the $j$-th smallest disc in category $i$. The judge will reply with the importance value at this position.
2. ! i j, which reports that the globally $k$-th smallest disc is the $j$-th smallest disc in category $i$.

2 2 2 22

222

? 2 2

! 2 2

Hint

Explanation for Sample 1

Dream's disc importance values are $[[2222,22222,222222],[22,222,2222222]]$.
Category 2 is $[22,222]$; the 2nd smallest importance in category 2 is $222$.
The globally 2nd smallest importance is also this disc.

Constraints

This problem uses bundled testdata.

For all testdata, $1 \le k \le n(2^m - 1)$. All disc importance values are pairwise distinct and are at most $10^{18}$.

Translated by ChatGPT 5