Border Maintenance in Gensokyo

This is an interactive problem.

Ran is helping Yukari to maintain the border of Gensokyo. The border is represented as a \(n \times m\) matrix, where both \(n\) and \(m\) are even. Unfortunately, due to the moving in of Moriya Shrine, there are exactly 4 weakened points in the matrix.

Ran has already determined a simple path from \((1,1)\) to \((n,m)\) by moving only right or down. This path separates the 4 weakened points into two groups with exactly 2 in each. The path will be provided in the input.

You can interact with the system by printing queries of the form ? x y to ask if the point \((x,y)\) is weakened. After each query, Ran will mark that point in blue. If your query reveals the \(k\)-th weakened point (and \(k\) is even), you must then output a simple path (a sequence of points ending with -1 -1) from the \((k-1)\)-th weakened point to the \(k\)-th weakened point. This path must pass through all blue marked points and no other points. After this, Ran will strengthen the points along your constructed path and recolor them red.

Note: You are only allowed to query points that are still white.

Your task is to eventually query and process all 4 weakened points and perform the required constructions. Once you have processed the fourth weakened point, your program should exit immediately.

Interaction Protocol:

• First, read two integers \(n\) and \(m\) from the standard input.
• Then, read several points (including the start and end points) from standard input, one per line, which represent a simple path from \((1,1)\) to \((n,m)\).
• You may then issue an unlimited number of queries of the form: ? x y.
• After each query, you will receive an integer \(p\) from the standard input. A \(p = 1\) indicates that the point \((x,y)\) is weakened; \(p = 0\) indicates it is not.
• On the \(k\)-th occasion (where \(k\) is even) that a query returns \(p = 1\), immediately output a simple path (one point per line, ending with -1 -1) from the \((k-1)\)-th weakened point to the \(k\)-th weakened point. This path must include all blue points and no other points.
• Exit your program immediately after processing the fourth weakened point and constructing the final path.

inputFormat

The input begins with two integers \(n\) and \(m\) (both even), representing the dimensions of the border matrix. This is followed by several lines, each containing two integers, representing the coordinates of a simple path from \((1,1)\) to \((n,m)\). The path ensures that exactly two weakened points lie on each side of it.

outputFormat

During interaction, your program will issue queries of the format ? x y to determine if a point is weakened. On every even occurrence of a weakened point discovery, output a simple path (one point per line, ending with -1 -1) connecting the last two discovered weakened points. This path must cover all blue-marked points and nothing else. Your program should terminate immediately after processing the fourth weakened point.

sample

2 2
1 1
1 2
2 2