CF2108D.Needle in a Numstack

这是一个交互式问题。

你在阁楼中发现了数字 $k$ 和 $n$，但丢失了两个数组 $A$ 和 $B$。

你记得以下信息：

• $|A| + |B| = n$，即两个数组的总长度为 $n$。
• $|A| \geq k$ 且 $|B| \geq k$，即每个数组的长度至少为 $k$。
• 数组中的元素只包含 $1$ 到 $k$ 的数字。
• 如果从数组 $A$ 中任取 $k$ 个连续元素，它们都互不相同。同样，如果从数组 $B$ 中任取 $k$ 个连续元素，它们也互不相同。

幸运的是，阁楼里的一个善良精灵找到了这两个数组，并将它们连接成一个长度为 $n$ 的数组 $C$。也就是说，数组 $C$ 的前半部分是 $A$ 的元素，后半部分是 $B$ 的元素。

你可以向精灵最多提出 $250$ 次询问。每次询问提供一个索引 $i$（$1 \leq i \leq n$），精灵会返回数组 $C$ 的第 $i$ 个元素。

你的任务是确定数组 $A$ 和 $B$ 的长度，或者报告无法唯一确定它们的长度。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 300$）。接下来是测试用例的描述。

每个测试用例仅包含一行，包含两个整数 $n$ 和 $k$（$1 \leq k \leq 50$，$2k \leq n \leq 10^6$）。

注意，所有测试用例的 $n$ 之和没有限制。

对于每个测试用例，交互开始时需要读取整数 $n$。

然后你可以进行最多 $250$ 次查询。

每次查询时，输出一个格式为 "? x"（不带引号）的字符串（$1 \leq x \leq n$）。每次查询后，读取一个整数——查询的答案。

如果你进行了过多的查询，将会得到 Wrong answer 的结果。

当你确定答案时，输出一个格式为 "! a b"（不带引号）的字符串，其中 $a$ 和 $b$ 分别是你找到的数组 $A$ 和 $B$ 的长度。这个回答不计入查询次数。

如果无法唯一确定数组的长度，输出 "! -1"（不带引号）。注意，如果存在不超过 $250$ 次查询即可唯一确定数组长度的情况下你回答 $-1$，将会得到 Wrong answer 的结果。

题目保证存在符合题目描述的数组 $A$ 和 $B$，且交互器的输出是正确的。

交互器是非自适应的，这意味着答案在参与者进行查询之前就已经确定，并且不会受到参与者查询的影响。

如果你的程序进行了超过 $250$ 次查询，应立即终止以避免 Wrong answer。否则，你的程序可能会因为继续读取已关闭的流而得到任意结果。

每次输出查询后，不要忘记换行并刷新输出缓冲区。否则，你可能会得到 "IL"（Idleness limit exceeded）的结果。刷新缓冲区的方法如下：

• C++：使用 fflush(stdout) 或 cout.flush()；
• Java：使用 System.out.flush()；
• Pascal：使用 flush(output)；
• Python：使用 stdout.flush()；
• 其他语言请参考相关文档。

考虑第一个例子。我们查询了数组 $C$ 的前 $3$ 个元素（共 $5$ 个）。现在我们知道了数组 $C$ 的前三个元素为 $[1, 2, 2, ?, ?]$。根据条件，数组 $A$ 中的任意 $k$（$k=2$）个连续元素必须互不相同，因此第三个元素 $2$ 不可能属于数组 $A$，它必定属于数组 $B$。由此可以确定数组 $A$ 的长度为 $2$，数组 $B$ 的长度为 $3$。

图中展示了所有测试用例的数组。被查询的元素用黄色标记。

翻译由 DeepSeek V3 完成