题目描述

This is an interactive problem.

Ran is helping Yukari to maintain the border of Gensokyo.

The border of Gensokyo is a $n\times m$ matrix, where $n$ and $m$ are both even. Unfortunately, due to Moriya Shrine's moving in, there are now $4$ weakened points within the matrix.

To ease the maintenance work, Ran have already found a path from $(1,1)$ to $(n,m)$, going only down or right. The path separates the four weakened points so that exactly two of them are on either side. She will tell you this path in the input.

Now you need to help Ran maintain the border. You can use the operation ? x y to ask whether the point $(x,y)$ is weakened. And after the query, Ran will mark the point with blue.

If, after a query, you have just found out the $k$-th weakened point, and $k$ is even, you will need to construct a simple path from the $(k-1)$-th weakened point to the $k$-th. The path you constructed must pass through and only pass through all the points that are marked blue. Ran will then strengthen these points in the border and recolor them red.

Ran does not want to do repetitive work, so you can only ask for points that are white with the ? query.

Now Ran hopes that you can ask all the "weakened points" and finish all the constructions.

Interaction Protocol

First read two integers $n$ and $m$ from standard input.

Then read several points (including start and end points) from standard input, one per line, representing a simple path from $(1,1)$ to $(n,m)$.

Then you can make unlimited queries. Print your queries to standard output in the format of ? x y. You will then receive an integer $p$ from standard input. If $p=1$, it means that the point you asked is indeed weakened; if $p=0$, it means that it is not weakened.

Remember to flush your output, you can use fflush(stdout); in C++. Please refer to your programming language's documentation.

On the $k$-th time ($k$ is even) of receiving the result $p=1$, please output several points (including the two weakened points) in order, one per line, ending with $-1,-1$, so that they represent the simple path from the $(k-1)$-th to the $k$-th weakened point.

You need to exit your program immediately after finding the fourth weakened point and finishing the construction.

输入格式

Refer to "Interactive Method".

输出格式

Refer to "Interactive Method".

题目大意

这是一道交互题。

有一个 $n\times m$ 的矩阵，保证 $n$ 和 $m$ 均为偶数。初始所有格子都是白色。用 $(x,y)$ 表示矩阵第 $x$ 行第 $y$ 列的格子。

矩阵中有四个关键点（也就是特殊的格子），并且保证存在一条从 $(1,1)$ 到 $(n,m)$ 的只能向下或向右的路径，将四个关键点分隔成两侧每侧两个。路径已被给出。

你可以用操作 ? x y 来询问格子 $(x,y)$ 是否为关键点（是的话交互器返回 $1$，否则返回 $0$），并且询问过后该格子会被染成蓝色。

在你第偶数次询问到关键点后，你需要输出一条从倒数第二次被询问到的关键点到最近一次询问到的关键点的简单路径，满足经过且仅经过所有被染成蓝色的格子。输出完成后，所有的蓝色格子都会变成红色。

需要注意，你只能询问白色格子。

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

提示

Explanation

The matrix in the sample is as follows:

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

Which X means a "weakened point".

Constraints

$4\le n,m\le100$。