题目背景

本题为 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 小重要度也是这音乐盘。

数据规模与约定

本题采用捆绑测试。

对于所有数据，$1\le k\le n(2^m-1)$，所有音乐盘的重要度互不相同并且小于等于 $10^{18}$。