Background

After carefully planning the workers' routes and executing all the plans, you finally have some money. You have contracted a larger mine and purchased more advanced equipment.

However, once you started operations, you discovered that some of the mineral transport channels were installed in reverse! Fortunately, they were designed to be reversible, and the central control system allows you to operate them easily.

The biggest problem now is that you have just taken over this mine, and you don't even know what it looks like, let alone which switch corresponds to which transport channel.

Time is money, and you want to figure out the structure of the entire mine and the correspondence between all switches and channels as quickly as possible.

Description

This is an interactive problem.

It is known that your mine has $n$ nodes, numbered $1 \sim n$. They are connected by $n-1$ transport channels to form a tree structure.

The transport channels are unidirectional. For a transport channel from node $u$ to node $v$, all minerals produced at node $u$ or transported to node $u$ can be transported to node $v$ at a high speed. If a node has multiple outgoing transport channels, the minerals are distributed equally among these channels.

The central control system includes $n-1$ switches and a monitor. The switches are numbered $1 \sim n-1$, and each switch can be set to position $0$ or $1$. The $n-1$ switches correspond one-to-one with the $n-1$ transport channels, but you do not know this correspondence. You only know that if the transport channel corresponding to switch $i$ was installed from $u_i$ to $v_i$, then when the switch is set to $0$, its transport direction is the same as when it was installed; when the switch is set to $1$, its transport direction becomes from $v_i$ to $u_i$. Your monitor can track how many different nodes the minerals arriving at each node originate from; that is, how many nodes (including itself) can transport minerals to this node through the transport channels.

After you adjust the positions of the switches, you need to wait for a period of time for the monitor's results to stabilize before the readings become meaningful. To avoid wasting too much time, you want to determine all the information you need within $50$ readings.

Input

Read data from standard input.

Initially, you need to input a positive integer $n$. It is guaranteed that $2 \le n \le 10000$.

Subsequent inputs will be generated based on your outputs. Your reading result is a line containing $n$ positive integers, where the $i$-th integer represents how many different nodes the minerals arriving at node $i$ originate from.

In each test case, the connection structure of the mine and the initial directions of all transport channels are fixed; that is, they will not be dynamically modified to another configuration consistent with previous answers based on your output.

Output

Output to standard output.

When you need to adjust the switches and wait for a reading, output a line ? s, where s is a 01 string of length $n-1$, and the $i$-th character represents the position of switch $i$. The interactive library will then provide the stabilized monitor readings via standard input. You can perform at most $50$ readings.

When you have determined the information for all channels, output a line ! u1 v1 ... un-1 vn-1, where $u_i, v_i$ indicate that the transport channel corresponding to switch $i$ was installed in the direction from node $u_i$ to node $v_i$.

After outputting a line, you must flush the output buffer; otherwise, the evaluation result may be TLE. Methods to flush the output buffer include:

• C: fflush(stdout);
• C++: fflush(stdout); or std::cout.flush(); or using std::endl
• Java: System.out.flush();
• Python: sys.stdout.flush()

Examples

Input 1

5

Output 1

? 0110

Input 2

1 4 1 2 3

Output 2

? 0000

Input 3

1 1 2 3 4

Output 3

! 1 4 2 3 2 4 4 5

Note

The initial directions of the channels are shown in the figure above. The numbers on the channels represent the IDs of the corresponding switches.

The example is only provided to illustrate the input/output format and reading results; it does not imply that these specific readings are sufficient to deduce the answer.

Evaluation

The execution time and memory of the interactive library are not counted towards the time and memory limits.

If the reading limit is exceeded, the final answer is incorrect, or the output format is incorrect, the evaluation result will be WA.