这是一个交互式问题。

评测系统隐藏了一棵有 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。这棵树有 $n-1$ 条边，第 $i$ 条边连接顶点 $s_i$ 和 $f_i$。你不知道这些边，但你可以向评测系统询问有关这棵树的问题。

你进行的每次询问必须包含一个顶点 $v$ 和一个长度为 $n-1$ 的二进制字符串 $b$。对于每次询问，评测系统会执行以下操作：

• 将这棵树视为以顶点 $v$ 为根的有根树。
• 树的每条边都被赋予方向。具体来说，如果 $b_i = 1$，则第 $i$ 条边被定向为从 $s_i$ 指向 $f_i$。否则，它被定向为从 $f_i$ 指向 $s_i$。
• 询问的答案是朝向根节点 $v$ 的边的数量。换句话说，答案是满足以下条件的树边的数量：该边起点到 $v$ 的距离大于该边终点到 $v$ 的距离。这里，两点之间的距离定义为它们在简单无向路径上的边数。

你的任务是在不超过 $10\,000$ 次询问内猜出所有的 $s_i$ 和 $f_i$。

交互格式

第一行包含一个整数 $n$ ($2 \le n \le 500$)，表示树的顶点数。

读取 $n$ 后，你可以进行不超过 $10\,000$ 次形式为 “? $v$ $b$” 的询问，其中 $v$ 是顶点编号 ($1 \le v \le n$)，$b$ 是长度为 $n-1$ 的二进制字符串。

对于每次询问，评测系统会返回一行，包含一个整数，表示朝向 $v$ 的边的数量。

当你准备好回答所有的 $s_i$ 和 $f_i$ 时，输出 “! $s_1$ $f_1$ $s_2$ $f_2$ ... $s_{n-1}$ $f_{n-1}$”。

你可以假设树本身以及所有的 $s_i$ 和 $f_i$ 在交互开始前就已经确定（即交互器是非自适应的）。

样例

样例输入 1

3
2
2
1

样例输出 1

? 1 01
? 2 00
? 3 11
! 2 3 2 1