说明

这是一道交互题。

中国象棋是一种在中国非常流行的双人策略棋盘游戏。中国象棋棋盘共有 $10$ 行 $9$ 列。我们用 $(r,c)$ 表示从下往上数第 $r$ 行、从左往右数第 $c$ 列的点（$0 \le r \le 9$，$0\le c \le 8$）。

:::align{center} :::

本题中涉及六种棋子：将（帅）、士、车、马、象（相）和兵（卒）。注意，炮不考虑在内。此外，所有棋子都可以移动到棋盘上的任何位置，这与原始规则略有不同。每种棋子的移动规则如下（假设当前位置为 $(r, c)$）：

$$\begin{array}{|c|c|c|} \hline \textbf{\text{棋子}} & \textbf{\text{符号}} & \textbf{\text{一次移动可到达的位置}} \\ \hline \text{将（帅）} & J & (r+1, c)\ (r-1, c)\ (r, c+1)\ (r, c-1) \\ \hline \text{士} & S & (r+1, c+1)\ (r+1, c-1)\ (r-1, c+1)\ (r-1, c-1) \\ \hline \text{车} & C & \text{所有满足 }r'=r\text{ 或 }c'=c\text{ 的 }(r', c')\text{，除了 }(r, c)\text{ 本身} \\ \hline \text{马} & M & (r+2, c+1)\ (r+2, c-1)\ (r-2, c+1)\ (r-2, c-1) \\ & & (r+1, c+2)\ (r+1, c-2)\ (r-1, c+2)\ (r-1, c-2) \\ \hline \text{象（相）} & X & (r+2,c+2)\ (r+2,c-2)\ (r-2,c+2)\ (r-2,c-2) \\ \hline \text{兵（卒）} & B & (r+1, c)\text{ 如果 }r \le 4\text{，否则 }(r+1,c)\ (r,c+1)\ (r,c-1) \\ \hline \end{array}$$

当然，棋子不能移出棋盘边界。现在你已经了解了规则，让我们开始游戏。

我在棋盘上放置了一枚棋子，你看不到它的位置或类型。但是，我会提供一个可能包含棋子位置的集合 $A$，其大小为 $n$。你的目标是使用最少的查询次数来确定棋子的类型。对于每次查询，你可以选择一个棋盘上的位置，我将告诉你棋子移动到该位置所需的最少步数，或者告诉你棋子不可能到达该位置。

这很有趣，不是吗？更有趣的是，我其实在暗中与你对抗。实话实说，尽管集合 $A$ 是固定的，但我并没有从一开始就固定这枚棋子的类型和位置。我的策略是调整对你每次查询的回应，以最大化你的查询次数，同时不与已给出的信息相矛盾。在我们双方都采用最优策略的情况下，你的查询次数 $m$ 实际上是可确定的。我相信你足够聪明，能够将其推算出来。游戏开始！

交互方式

首先，你应该从标准输入读取一个整数 $n$（$1\le n\le 90$），表示集合 $A$ 的大小。

然后，读取 $n$ 行。每行包含两个整数 $r$ 和 $c$，表示集合 $A$ 中的一个位置。保证所有位置互不相同。

读取这 $n+1$ 行后，你应该向标准输出输出一个整数 $m$，表示查询次数。如果你的输出 $m$ 不正确，你将得到 Wrong answer 的判定。然后你必须恰好进行 $m$ 次查询。

要进行一次查询，请在一行中输出 ? r c（$0\le r\le 9, 0\le c\le 8$）。然后你应该从标准输入读取一个整数，表示棋子移动到所选位置所需的最少步数，如果棋子无法移动到该位置，则为 $-1$。如果你的程序进行了无效查询或超过了查询次数，交互器将立即终止，你将收到 Wrong answer 的判定。

要输出你对棋子类型的猜测，你需要输出 ! ch，其中 ch 表示题目描述中代表该棋子的符号。

在你进行一次查询或输出你的答案（包括 $m$ 和棋子类型）后，请不要忘记输出换行符 \n 并刷新输出缓冲区。为此，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Python 中的 stdout.flush()。

1
9 0


6

1
? 3 6

! S

4
2 1
2 3
2 5
2 7


3

1

2
? 0 0

? 2 0

! J

提示

对于第一个示例，六种棋子从位置 $(9, 0)$ 移动到 $(3, 6)$ 所需步数如下：

$$\begin{array}{|c|c|c|c|c|c|} \hline \text{将（帅） (J)} & \text{士 (S)} & \text{车 (C)} & \text{马 (M)} & \text{象（相） (X)} & \text{兵（卒） (B)} \\ \hline 12 & 6 & 2 & 4 & 3 & -1 \\ \hline \end{array}$$

因此，你只需要进行一次查询即可确定答案。

翻译由 DeepSeek V3 完成