P11493 [BalticOI 2023] Mineral Deposits

**这是一道交互题**。 平面上有 $k$ 个**不同的**整点，其横纵坐标都在 $[-b,b]$ 中。每次询问你可以给定不超过 $2\,000$（设为 $d$）**不同**的整点，交互库会告诉你所有这些整点到原先的整点的曼哈顿距离（共 $kd$ 个）的可重集。 你要在 $w$ 次询问中求出这 $k$ 个整点，且所有询问的 $d$ 之和不能超过 $2\times10^4$。 平面上两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的曼哈顿距离定义为 $|x_1-x_2|+|y_1-y_2|$。 **【交互格式】** 首先选手程序读入一行三个正整数 $b,k,w$。 接下来选手可以进行不超过 $w$ 次询问，每次询问形如 $\texttt{?}\ s_1\ t_1\ s_2\ t_2\ \cdots\ s_d\ t_d$，表示你询问的点为 $(s_1,t_1),(s_2,t_2),\cdots,(s_d,t_d)$。你需要保证 $-10^8\le s_i,t_i\le 10^8$，且$d\le 2\,000$，且 $\sum d\le 2\times10^4$ 且一个询问中的 $(s_i,t_i)$ 互不相同。 每次询问后，你需要从标准输入中读入一行 $kd$ 个不降的非负整数，表示所有距离组成的可重集。 如果你确定了所有 $k$ 个点的坐标，则输出一行 $\texttt{!}\ x_1\ y_1\ x_2\ y_2\ \cdots\ x_k\ y_k$ 表示这 $k$ 个点的坐标为 $(x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)$。**你可以以任意顺序输出这 $k$ 个点。** **每次询问后，你需要清空缓冲区。**

见「交互格式」。

见「交互格式」。

**【样例解释】** 第一次询问得到的回答分别为 $2=|(-4)-(-3)|+|(-3)-(-2)|,4=|(-1)-1|+|0-2|,4=|2-1|+|(-1)-2|,4=|(-1)-(-3)|+|0-(-2)|,6=|2-(-3)|+|(-1)-(-2)|,10=|(-4)-1|+|(-3)-2|$。 第二次询问得到的回答分别为 $0=|1-1|+|2-2|,3=|0-(-3)|+|(-2)-(-2)|,5=|0-1|+|(-2)-2|,8=|1-(-3)|+|2-(-2)|$。 需要注意的是，样例仅为展示交互格式，给出的信息并不足以确定答案。 **【数据范围】** 对于 $100\%$ 的数据，$1\le b\le 10^8$，$1\le k\le 20$，$2\le w\le 10^4$。 | 子任务编号 | 分值 | 特殊限制 | | :----------: | :----------: | :----------: | | $1$ | $9$ | $k=1$，$w=10^4$ | | $2$ | $19$ | $w\ge 500$ | | $3$ | $11$ | $w\ge 210$ | | $4$ | $7$ | $w\ge 130$ | | $5$ | $20$ | $w\ge 3$，$b\le 10^4$ | | $6$ | $15$ | $w\ge 3$，$b\le 10^7$ | | $7$ | $19$ | 无特殊限制 |