这是一个交互式问题，且评测系统是自适应的。

给定一个包含 $N$ 个顶点的完全无向图 $G$。每条边都被染成红色或蓝色，但颜色是隐藏的。

你可以进行最多 $2N$ 次以下类型的询问：

• 询问连接顶点 $i$ 和顶点 $j$ 的边 $(i, j)$ 的颜色 ($1 \le i, j \le N, i \neq j$)。

输出图 $G$ 的一棵生成树，要求其中所有边的颜色相同。题目保证在给定的约束条件下，这样的生成树一定存在。

注意，输出不计入询问次数。

交互

首先，从标准输入读取一个整数 $N$：图中的顶点数 ($2 \le N \le 5 \times 10^4$)。

之后，你可以进行询问。若要询问连接顶点 $i$ 和顶点 $j$ 的边 $(i, j)$ 的颜色 ($1 \le i, j \le N, i \neq j$)，请按以下格式输出一行（末尾包含换行符）：

? i j

如果询问有效，你将收到一个响应 $c$：边 $(i, j)$ 的颜色，如果边为红色则为 R，如果边为蓝色则为 B。

如果询问因格式错误或超过允许的询问次数而无效，你将收到 F。

在这种情况下，你的提交将被判为错误，评测程序将终止。

当你确定了要输出的生成树 $T$ 时，请按以下格式输出答案（末尾包含换行符）。每条边 $(u_i, v_i)$ 应按如下方式输出：

!
u1 v1
u2 v2
.
.
.
uN−1 vN−1

只有满足以下所有条件，答案才会被视为正确：

• $1 \le u_i, v_i \le N, u_i \neq v_i$
• 由这 $N - 1$ 条边及其顶点组成的图是 $G$ 的一棵生成树。
• 所有 $N - 1$ 条边的颜色相同。

一旦接收到答案，评测程序将终止，无论答案是否正确。

样例

样例输入 1

3
R
B
R

样例输出 1

? 1 2
? 1 3
? 2 3
!
1 2
2 3