Strange device
Contest: Codeforces Round 559 (Div. 1)
Difficulty rating: 3400
Tags: binary search, interactive, math, trees

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 format:
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 < 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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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) > 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.

Example input:
5
00000
11011
11100
10010

Example output:
? 0 0 0 0 0
? 1 1 2 0 2
? 0 0 0 1 0
? 0 1 0 0 1
!
4 2
1 5
3 4
4 1

Editorial:
The solution will consist of two parts.
1 part
Let's divide all points into sets with equal distance to the vertex $$$1$$$. To do this, we will do the following algorithm. How to understand what set of points lies at a distance $$$\lfloor \frac{n}{2} \rfloor$$$ from the top of $$$1$$$? Let's fill $$$d$$$ with zeros and make $$$d_1 = \lfloor \frac{n}{2} \rfloor$$$ for the first operation and $$$d_1 = \lfloor \frac{n}{2} \rfloor - 1$$$ for the second operation. After that we will make $$$2$$$ operations with such $$$d$$$ arrays. Those vertices whose bulbs did not light up during the first operation lie at a distance of $$$> \lfloor \frac{n}{2} \rfloor$$$. Those that caught fire at the first, but did not catch fire at the second operation lie at a distance of $$$\lfloor \frac{n}{2} \rfloor$$$. Finally, those who caught fire during the second operation lie at a distance of $$$< \lfloor \frac{n}{2} \rfloor$$$. Generalize this idea. We will store the set of distances for which we already know the set of vertices at lying such distance from $$$1$$$ (we will call them good distances). Initially it is $$$0$$$ (only vertex $$$1$$$ at distance $$$0$$$) and $$$n$$$ (empty vertex set at distance $$$n$$$). We will also store between each pair of adjacent good distances $$$l_1 < l_2$$$ those vertices for which the distance is greater than $$$l_1$$$, but less than $$$l_2$$$. Now let's iterate over pairs of adjacent good distances $$$l_1 < l_2$$$. Take $$$m = \lfloor \frac{l_1 + l_2}{2} \rfloor$$$. Now the sets of vertices lying at distances greater than $$$l_1$$$, but less than $$$m$$$, exactly $$$m$$$ and more than $$$m$$$, but less than $$$l_2$$$ can be obtained using the two operations described at the beginning. With this action, we make $$$m$$$ a good distance. To do this in parallel for several pairs of adjacent good distances just iterate over pairs with even numbers and odd ones. Then as each of the cases would not be adjacent pairs, you can make two common operations. Thus, with the help of $$$4$$$ operations, we will make the middle between all pairs of adjacent good distances also a good distance. If we divide in half, then for $$$\lceil \log{n} \rceil$$$ of divisions we will make all distances good. At this part we will spend $$$4 \lceil \log{n} \rceil$$$ operations.
2 part
For each vertex at the distance of $$$l > 0$$$ let's find the index of the ancestor vertex lying at a distance of $$$l-1$$$ (which is the only one). Suppose we want to do this for only one distance $$$l > 0$$$. Note that if we make $$$d_v = 1$$$ for all $$$v \in S$$$, for some subset of vertices $$$S$$$ lying at a distance $$$l-1$$$, and for all other vertices $$$0$$$, then among the vertices at a distance $$$l$$$ will include those whose ancestor belongs to $$$S$$$. Then let's for all $$$i$$$ such that $$$2^i < n$$$ choose $$$S$$$ as the set of vertices $$$v$$$ such that $$$v - 1$$$ contains $$$i$$$-th bit in binary notation and lies at a distance of $$$l-1$$$. Then, for each vertex at a distance of $$$l$$$, we will know all the bits in the binary representation of its ancestor, that is, we will find this number. This process can also be done in parallel, if we take the distance $$$l$$$, giving the same remainder of dividing by $$$3$$$. Then, since these distances are not close, they will not interfere with each other. At this part we will spend $$$3 \lceil \log{n} \rceil$$$ operations.
In total we get a solution using $$$7 \lceil \log{n} \rceil$$$ operations.
Complexity: $$$O(n \log{n})$$$.
Number of operations: $$$7 \lceil \log{n} \rceil$$$.