「MCOI-07」Dream and More Discs

**本题为 IO 交互题。**

Dream 将 Tommy 的所有音乐盘分为 $n$ 类，其中第 $i$ 类有 $2^m-1$ 片音乐盘。所有盘都有一个唯一的正整数重要度。 现在 Dream 已经把所有类之内的音乐盘按照重要度递增排序。Dream 想知道**所有**盘中重要度第 $k$ 小是哪个盘。 由于音乐盘数量实在太多，Dream 不能直接给你所有音乐盘的重要度。在寻找答案时，Dream 允许你访问第 $i$ 类重要度第 $j$ 小的盘重要度值。

交互开始时，评测机输入第一行为四个正整数 $n$，$m$，$k$，和 $Th$，其中 $Th$ 为最多应用访问次数。 每一次访问，评测机会回复所访问位置的音乐盘重要度。

你的程序可以进行两个操作： 1. `? i j`，表示访问第 $i$ 类型第 $j$ 小音乐盘重要度。评测机会回复这位置重要度。 2. `! i j`，表示报告全局第 $k$ 小音乐盘为第 $i$ 类的第 $j$ 小音乐盘。

2 2 2 22

222

? 2 2

! 2 2

#### 样例 1 解释 Dream 的音乐盘重要度为 $[[2222,22222,222222],[22,222,2222222]]$。 第 2 类型为 $[22,222]$；第 2 类型的第 2 小重要度为 $222$。 全局第 2 小重要度也是这音乐盘。 #### 数据规模与约定 **本题采用捆绑测试。** | Subtask | 分值 | $n$ | $m$ | $k$ | $Th$ | | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | | 1 | 1 pts | $1$ | $1$| $1$| $15,000$ | | 2 | 9 pts | $50$ | $8$ | 无 | $15,000$ | | 3 | 19 pts | $20$ | $11$ | 无 | $15,000$ | | 4 | 17 pts | $50$ | $11$ | 无 | $6,666$ | | 5 | 23 pts | $50$ | $11$ | 无 | $2,333$ | | 6 | 31 pts | $50$ | $11$ | 无 | $1,111$ | 对于所有数据，$1\le k\le n(2^m-1)$，所有音乐盘的重要度互不相同并且小于等于 $10^{18}$。