题目背景

本题为交互题。

题目描述

Troy 要和您一起玩游戏，他的游戏要用一个 $R \times C$ 的棋盘。

现在给定 $N$ 个棋子（从 $1$ 编号到 $N$），第 $i$ 个棋子放置在 $(X_i,Y_i)$ 处，同一格可能有多个棋子。

Troy 可以在一秒内将一个棋子移动到与其垂直或水平相邻的格子中，格子的分数就被 Troy 定义为将这 $N$ 个棋子挪到这个格子的秒数的最小值，您要做的就是找棋盘中格子里的分数的最小值。

Troy 不会告诉您 $N$ 的值和每个棋子的位置，但是您可以问 Troy 最多 $K$ 个问题：格子 $(p,q)$ 的分数。

交互策略

本题为交互题。

首先，读入三个整数 $R,C,K$ 代表整个棋盘的大小，和您最多能问多少个问题。

读入完这一行后，您的程序将会对提出关于 $(p,q)$ 的分数的问题（格式为 ? p q），然后您就会得到一个整数 $s$ 带包这个格子的分数。

一旦您的程序确定了棋盘中的格子的分数的最小值，那么就会输出 ! Z 并终止程序，$Z$ 就代表最终结果。

在输出每一行后，都应刷新缓冲区：

• C/C++：fflush(stdout) or cout << endl
• Java：System.out.flush()
• Pascal：flush(output)

如果您输出的格式有误，或者提出的问题超过了 $K$ 个，您的答案就是错误的。

输入格式

None

输出格式

None

1 10 90 3
1 2
1 4
1 10

5 4 170 4
2 3
2 3
4 3
5 1

提示

样例说明

对于样例 $1$

请求	回答
	1 10 90
? 1 3	9
? 1 7	11
? 1 4	8
! 8

棋子的位置应该在 $(1,2)$，$(1,4)$ 和 $(1,10)$，所以我们得到的所有棋盘上的分数的最小值为 $8$（格子 $(1,4)$ 的分数）。

对于样例 $2$

请求	回答
	5 4 170
? 2 4	11
? 1 4	15
? 3 3	7
! 7

棋子的位置应该在 $(2,3)$，$(2,3)$，$(4,3)$，$(5,1)$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le R,C \le 10^7$，$1 \le K \le 170$，$1 \le p\le R$，$1 \le q \le C$，$0 \le s \le 2 \times 10^9$，$1 \le N \le 100$，$1 \le X_i \le R$，$1 \le Y_i \le C$。
对于 $20\%$ 的数据，$R=1$，$C \le 90$，$K=90$。
对于另外 $20\%$ 的数据，$R=1$，$K=90$。
对于另外 $20\%$ 的数据，$K = 170$。
对于另外 $20\%$ 的数据，$K = 100$。
对于另外 $20\%$ 的数据，$K=75$。

spj 和交互库见附加文件。

说明

翻译自 Canadian Computing Olympiad 2018 Day 2 A Gradient Descent。

spj 作者：