Chinese chess is a two-player strategy board game that is very popular in China. There are rows and columns on a Chinese chess board. We denote the point on the -th row from bottom to top and on the -th column from left to right by (, ).
:::align{center}
:::
There are six types of pieces in this problem: kings, mandarins, rooks, knights, bishops, and pawns. Note that cannons are not considered. Additionally, all pieces can be moved anywhere on the board, which differs slightly from the original rules. The movement rules for each piece are as follows (assuming the current position is ):
Of course, pieces cannot move outside the board's boundaries. Now that you understand the rules, let's play a game.
I have placed a piece on the board, and you cannot see its position or type. However, I will provide a set of possible positions where the piece might be located. Your goal is to determine the type of the piece using the minimum number of queries. For each query, you can select a position on the board, and I will tell you the minimum number of moves required for the piece to move to that position, or I will tell you if it is impossible for the piece to reach that position.
Interesting, isn't it? What is even more interesting is that I am actually gaming against you in secret. Truth be told, although set is fixed, I have not fixed the type and position of this piece from the start. My strategy is to adjust the answer to each of your queries in a way that maximizes the number of queries you make, without contradicting the information already given. In the case where both of our strategies are optimal, your number of queries is actually determinable. I am sure you are smart enough to figure it out. Let the game begin!
Interaction Protocol
Firstly, you should read an integer () from standard input, indicating the size of the set .
Then, read lines. Each line contains two integers and , indicating a position in the set . All positions are guaranteed to be distinct.
After reading these lines, you should output an integer to standard output, indicating the number of queries. If your output is incorrect, you will get a verdict. You must then make exactly queries.
To make a query, output () in a single line. Then you should read an integer from standard input, indicating the minimum number of moves required for the piece to reach the selected position, or if the piece cannot move to that position. If your program makes an invalid query or exceeds the number of queries, the interactor will terminate immediately, and you will receive a verdict.
To output your guess about the type of the piece, you need to output , where means the symbol representing the piece that is shown in the statement.
After you make a query or output your answer, including the and the type of the piece, do not forget to output the End of Line and flush the output. To do this, use:
or in C++;
in Java;
in Python;
样例
样例输入 1
1
9 0
6
样例输出 1
1
? 3 6
! S
样例输入 2
4
2 1
2 3
2 5
2 7
3
1
样例输出 2
2
? 0 0
? 2 0
! J
数据范围与提示
For the first example, the number of moves required for each of the six types of pieces to move from position to is as follows:
Thus, you only need to make one query to determine the answer.
:::