CF1158E.Strange device

It is an interactive problem.

Vasya enjoys solving quizzes. He found a strange device and wants to know how it works.

This device encrypted with the tree (connected undirected graph without cycles) with $n$ vertices, numbered with integers from $1$ to $n$. To solve this quiz you should guess this tree.

Fortunately, this device can make one operation, using which you should guess the cipher. You can give the device an array $d_1, d_2, \ldots, d_n$ of non-negative integers. On the device, there are $n$ lamps, $i$-th of them is connected with $i$-th vertex of the tree. For all $i$ the light will turn on the $i$-th lamp, if there exist such vertex of the tree with number $j \neq i$ that $dist(i, j) \leq d_j$. Let's define $dist(i, j)$ as the distance between vertices $i$ and $j$ in tree or number of edges on the simple path between vertices $i$ and $j$.

Vasya wants to solve this quiz using $\leq 80$ operations with the device and guess the tree. Help him!

Interaction

In the beginning, your program should read one integer $n$ — the number of vertices of the tree which encrypts the device ($2 \leq n \leq 1000$).

After that, you can make several operations in the following format. To do operation print a symbol"?" (without quotes) and $n$ integers $d_1, d_2, \ldots, d_n$, separated by spaces after it. Please note, that for all $i$ you can only use the numbers, satisfying the inequality $0 \leq d_i \lt n$. After that, you should read a string $s$ with length $n$, consisting of symbols "0" and "1" (without quotes). For all $i$ the symbol $s_i$ is equal to "0", if the lamp on the device, connected with $i$-th vertex of the tree is switched off and "1" otherwise.

After several operations, you should print guessed tree. To do it print the only symbol "!" (without quotes). In the next $n-1$ lines print $2$ integers $a_i$, $b_i$ — indexes of the vertices connected by $i$-th edge of the tree. This numbers should satisfy the conditions $1 \leq a_i, b_i \leq n$ and $a_i \neq b_i$. This edges should form a tree, which is equal to the hidden tree. After that, your program should terminate.

It is guaranteed, that in each test the tree is fixed before and won't change depending on your program's operations.

Your program can make from $0$ to $80$ operations with the device and after that guess the tree equal with the hidden.

If your program will make more than $80$ operations it can get any verdict, because it will continue reading from closed input. If your program will make operation or print the answer in the incorrect format, it can get any verdict too. Be careful.

Don't forget to flush the output after printing questions and answers.

To flush the output, you can use:

• fflush(stdout) in C++.
• System.out.flush() in Java.
• stdout.flush() in Python.
• flush(output) in Pascal.
• See the documentation for other languages.

Hacks:

The first line should contain one integer $n$ — the number of vertices in the tree ($2 \leq n \leq 1000$). Next $n-1$ lines should contain $2$ integers $a_i$, $b_i$ — indexes of the vertices connected by $i$-th edge of the tree ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$). All edges should form a tree. Be careful, extra spaces or line breaks are not allowed.

这是一个交互式问题。

瓦西娅喜欢解谜题。他发现了一个奇怪的设备，并想知道它的工作原理。

该设备使用一棵树（即一个无环的连通无向图）进行加密，树上有 $n$ 个顶点，编号为 $1$ 到 $n$。要解开这个谜题，你需要猜出这棵树。

幸运的是，该设备支持一种操作，你需借助该操作来破解加密。你可以向设备提供一个由 $n$ 个非负整数组成的数组 $d_1, d_2, \ldots, d_n$。设备上有 $n$ 盏灯，其中第 $i$ 盏灯连接到树上的第 $i$ 个顶点。对于每个 $i$，若存在树上某个编号为 $j \neq i$ 的顶点，使得 $dist(i, j) \leq d_j$，则第 $i$ 盏灯将被点亮。我们定义 $dist(i, j)$ 为树中顶点 $i$ 与 $j$ 之间的距离，即两点间简单路径上的边数。

瓦西娅希望至多使用 $80$ 次设备操作来解开这个谜题并猜出这棵树。请帮助他！

交互方式

程序开始时，应先读入一个整数 $n$ —— 表示设备所加密的树的顶点数（$2 \leq n \leq 1000$）。

之后，你可以执行若干次如下格式的操作：输出一个字符 "?"（不带引号），后跟 $n$ 个用空格分隔的整数 $d_1, d_2, \ldots, d_n$。注意：对所有 $i$，你只能使用满足不等式 $0 \leq d_i < n$ 的整数。随后，你需要读入一个长度为 $n$ 的字符串 $s$，其仅由字符 "0" 和 "1"（不带引号）组成。对每个 $i$，若连接树上第 $i$ 个顶点的灯处于关闭状态，则 $s_i = \text{"0"}$；否则 $s_i = \text{"1"}$。

执行若干次操作后，你需要输出所猜测的树。为此，首先单独输出一个字符 "!"（不带引号）。接着，在接下来的 $n-1$ 行中，每行输出两个整数 $a_i$、$b_i$ —— 表示树中第 $i$ 条边所连接的两个顶点的编号。这些数必须满足 $1 \leq a_i, b_i \leq n$ 且 $a_i \neq b_i$。这些边必须构成一棵树，且必须与隐藏的树完全相同。此后，你的程序应终止。

保证在每个测试用例中，隐藏的树在交互开始前即已固定，不会根据你的程序操作而改变。

你的程序最多可执行 $0$ 至 $80$ 次设备操作，然后输出一棵与隐藏树完全相同的树。

如果你的程序执行了超过 $80$ 次操作，则可能得到任意判定结果，因为此时输入流已关闭，程序将继续尝试从中读取数据。如果你的程序执行了格式错误的操作，或以错误格式输出答案，也可能得到任意判定结果。请务必谨慎。

在输出询问和答案后，请勿忘记刷新输出缓冲区。

刷新输出的方法包括：

• C++ 中使用 fflush(stdout)；
• Java 中使用 System.out.flush()；
• Python 中使用 stdout.flush()；
• Pascal 中使用 flush(output)；
• 其他语言请参阅相应文档。

Hack 输入格式

第一行应包含一个整数 $n$ —— 树的顶点数（$2 \leq n \leq 1000$）。接下来 $n-1$ 行，每行包含两个整数 $a_i$、$b_i$ —— 表示树中第 $i$ 条边所连接的两个顶点的编号（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$）。所有边必须构成一棵树。注意：不允许出现额外空格或换行符。

It is a picture of the tree which encrypt the device from the first test:

It is a table of pairwise distances between vertices in this tree:

• If you make operation where $d = [0, 0, 0, 0, 0]$, no lamp will switch on, because $dist(i, j) \gt 0$ for all $i \neq j$.
• If you make operation where $d = [1, 1, 2, 0, 2]$, all lamps except the lamp connected with the $3$-rd vertex will switch on. For example, lamp connected with the $1$-st vertex will switch on, because $dist(1, 5) = 1 \leq 2 = d_5$.
• If you make operation where $d = [0, 0, 0, 1, 0]$, all lamps except lamps connected with the $4$-th and $5$-th vertices will switch on.
• If you make operation where $d = [0, 1, 0, 0, 1]$, only lamps connected with the $1$-st and $4$-th vertices will switch on.

这是第一组测试中用于加密设备的树的图片：

这是该树中各顶点两两之间距离的表格：

• 若执行操作 $d = [0, 0, 0, 0, 0]$，则没有任何灯会亮起，因为对所有 $i \neq j$ 均有 $dist(i, j) \gt 0$。
• 若执行操作 $d = [1, 1, 2, 0, 2]$，则除连接第 $3$ 个顶点的灯外，其余所有灯均会亮起。例如，连接第 $1$ 个顶点的灯会亮起，因为 $dist(1, 5) = 1 \leq 2 = d_5$。
• 若执行操作 $d = [0, 0, 0, 1, 0]$，则除连接第 $4$ 个和第 $5$ 个顶点的灯外，其余所有灯均会亮起。
• 若执行操作 $d = [0, 1, 0, 0, 1]$，则仅有连接第 $1$ 个和第 $4$ 个顶点的灯会亮起。