题目描述

译自 Canadian Computing Olympiad 2018 Day 2 A Gradient Descent

Troy 要和你一起玩游戏，规则如下。

他有一个 $R$ 行 $C$ 列的棋盘。每行按从 $1$ 到 $R$ 的顺序编号，每列按从 $1$ 到 $C$ 的顺序编号。令第 $p$ 行第 $q$ 列的单元格为 $(p,q)$。

现在给定 $N$ 个棋子（从 $1$ 编号到 $N$），第 $i$ 个棋子放置在 $(X_i,Y_i)$ 处，其中 $1\le X_i\le R,1\le Y_i\le C$。同一格可能有多个棋子。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$ 个，将返回答案错误。

对于每组测试数据，$N,R,C,K$ 和每个棋子的坐标在程序运行时都是固定的。也就是说，交互系统不是适应性的。

样例交互过程 1

样例解释

在这个样例中，棋子放在 $(1,2),(1,4),(1,10)$。保证测试中使用的样例与这个样例一致。

单元格 $(1,3)$ 的分数为 $1 + 1 + 7 = 9$。

单元格 $(1,7)$ 的分数为 $5 + 3 + 3 = 11$。

单元格 $(1,4)$ 的分数为 $2 + 0 + 6 = 8$，并且是分数最小的单元格。

这个样例中分数如下表：

样例交互过程 2

样例解释

在这个样例中，棋子放在 $(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$。