这是一个交互式问题。

在 Berland，有两家航空公司：Aeroshipping 和 Wicktory（之前称为 Kindplane）。由于 Berland 是一个发达国家，对于每一对城市，都有一家航空公司提供它们之间的航班。由于 Berland 是一个节约的国家，对于每一对城市，只有一家航空公司提供航班。

Berland 的城市编号从 $1$ 到 $n$（因此 Berland 共有 $n$ 个城市）。一位游客想要环游 Berland，也就是说，他想要访问每个城市恰好一次，并回到他出发的城市结束旅程。出发城市可以任意选择。

由于游客不想惹恼航空公司的员工，他希望更换航空公司的次数不超过一次。不幸的是，游客不知道哪家航空公司控制着每一条可能的航线。为了了解这一点，他可以询问形式为“哪家航空公司控制从城市 $u$ 到城市 $v$ 的航班？”的问题。显然，游客不想浪费太多时间，所以他决定询问不超过 $2n$ 个这样的问题。

请帮助游客制定这样一条路线！保证答案存在。

交互

首先，你只会得到整数 $n$，即 Berland 的城市数量（$3 \le n \le 777$）。

每次你想知道哪家航空公司连接城市 $u$ 和 $v$（$1 \le u, v \le n; u \neq v$）时，请打印单行 “? $u$ $v$”。

每次询问后，你将得到一行包含一个字符的反馈，该字符为 “A” 或 “W”：代表连接相应城市对的航空公司名称的首字母。

如果你进行了超过 $2n$ 次询问，你的程序将被终止，结果为 “Wrong Answer”。

当你准备好提供路线时，请打印单行 “! $a_1$ $a_2$ ... $a_n$”，按访问顺序列出你旅程中的城市编号。在这次旅程中，所有相邻城市之间的航班必须由同一家航空公司提供，或者必须存在一个整数 $k$，使得 $a_1, \dots, a_k$ 之间的所有相邻城市航班由一家航空公司提供，而 $a_k, \dots, a_n, a_1$ 之间的所有相邻城市航班由另一家航空公司提供（记住，游客在旅程结束时必须从 $a_n$ 飞回 $a_1$！）。保证至少存在一个满足上述约束的解。

打印路线后，你的程序必须立即退出。

不要忘记在每行末尾添加换行符，并在每次询问后刷新输出。

样例

输入 1

5
A
A
W
W
W

输出 1

? 1 5
? 5 4
? 4 3
? 3 2
? 2 1
! 1 5 4 3 2