Description

这是一个交互式问题。

Ran 正在帮助 Yukari 维护幻想乡的边界。

幻想乡的边界是一个 $n \times m$ 的矩阵，其中 $n$ 和 $m$ 都是偶数。不幸的是，由于 Moriya 神社的迁入，矩阵中现在有 4 个薄弱点。

为了简化维护工作，Ran 已经找到了从 $(1,1)$ 到 $(n,m)$ 的一条路径，只能向下或向右走。路径将四个薄弱点分隔开，使得每一侧恰好有两个薄弱点。她将在输入中告诉你这条路径。

现在你需要帮助 Ran 维护边界。你可以使用操作 ? x y 来询问点 $(x,y)$ 是否是薄弱点。在查询之后，Ran 会将该点标记为蓝色。

如果在一次查询后，你刚刚找到了第 $k$ 个薄弱点，并且 $k$ 是偶数，你需要构造一条从第 $(k-1)$ 个薄弱点到第 $k$ 个薄弱点的简单路径。你构造的路径必须经过且仅经过所有标记为蓝色的点。Ran 然后将这些点在边界上加固并重新着色为红色。

Ran 不想做重复的工作，所以你只能用 ? 查询白色的点。

现在 Ran 希望你能找到所有的“薄弱点”并完成所有的构造。

交互协议

首先从标准输入读取两个整数 $n$ 和 $m$。

然后从标准输入读取几个点（包括起点和终点），每行一个，表示从 $(1,1)$ 到 $(n,m)$ 的一条简单路径。

然后你可以进行无限次查询。将你的查询以 ? x y 的格式打印到标准输出。然后你将从标准输入接收一个整数 $p$。如果 $p=1$，表示你询问的点确实是薄弱点；如果 $p=0$，表示它不是薄弱点。

记得刷新你的输出，你可以在 C++ 中使用 fflush(stdout);。请参考你的编程语言的文档。

在第 $k$ 次（$k$ 是偶数）接收到结果 $p=1$ 时，请按顺序输出几个点（包括两个薄弱点），每行一个，以 $-1,-1$ 结束，以表示从第 $(k-1)$ 个到第 $k$ 个薄弱点的简单路径。

在找到第四个薄弱点并完成构造后，你需要立即退出程序。

Input Format

参考“交互方法”。

Output Format

参考“交互方法”。

4 4
1 1
1 2
2 2
3 2
3 3
3 4
4 4

0

1

0

0

1







1

1

? 2 2

? 2 1

? 3 1

? 3 2

? 4 1

2 1
2 2
3 2
3 1
4 1
-1 -1
? 1 4

? 1 3

1 4
1 3
-1 -1

Hint

解释

示例中的矩阵如下：

..XX
X...
....
X...

其中 X 表示一个“薄弱点”。

约束

$4 \le n,m \le 100$。

题面翻译由 ChatGPT-4o 提供。