H. How to Validate Such a Program
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

KUPC-kun wrote a program that solves the following problem.

You are given a tree $$$T=(V,E)$$$ with $$$N$$$ vertices.
For a sequence $$$\{a_1,\ldots,a_{k}\}$$$ of vertices of $$$T$$$ of length $$$k$$$, define its score as follows.
- Let $$$d(u,v)$$$ be the number of edges on the path between vertices $$$u$$$ and $$$v$$$ in $$$T$$$. Then the score is
$$$\prod_{i=1}^{k} d(a_i,a_{(i \bmod k)+1})$$$
A subset $$$S$$$ of $$$V$$$ is given. For each $$$1 \leq k \leq N$$$, find the following value $$$q_k$$$.
- The sum of the scores over all vertex sequences $$$\{a_1,\ldots,a_{k}\}$$$ of length $$$k$$$ whose elements belong to $$$S$$$,
taken modulo $$$2^{61}-1$$$

KUPC-kun secretly keeps the information of the tree $$$T$$$ in advance, and continues using $$$T$$$ as the tree given to the program.

You are trying to recover the information of the leaves using the above program. Letting the number of vertices of the tree be $$$N$$$, you may ask the following question at most $$$N$$$ times.

  • Choose a subset $$$S$$$ of $$$V$$$ and ask for the output of the program.

Assuming that KUPC-kun's program is correct, identify all leaves contained in the tree $$$T$$$ from the information obtained through the questions.

The judge is not adaptive, and the tree $$$T$$$ is fixed before the interaction begins.

Interaction

First, $$$N$$$ is given from standard input. ($$$2 \leq N \leq 50$$$)

For each question, output to standard output in the following format.

? $$$s_1s_2\cdots s_N$$$

Here, $$$s_1s_2\cdots s_N$$$ is a string of length $$$N$$$ representing the subset $$$S$$$, where $$$s_i=1$$$ if $$$i \in S$$$, and $$$s_i=0$$$ if $$$i \notin S$$$.

In response, the following is given from standard input.

$$$q_1$$$ $$$q_2$$$ $$$\cdots$$$ $$$q_N$$$

Once you have identified all leaves, output your answer in the following format.

! $$$t_1t_2\cdots t_N$$$

Here, $$$t_1t_2\cdots t_N$$$ is a string of length $$$N$$$, where $$$t_i=1$$$ if $$$i$$$ is a leaf, and $$$t_i=0$$$ if it is not a leaf.

After this output, terminate your program immediately.

Whenever you output something, append a newline at the end and flush standard output.

Example
Input
5

0 8 0 32 0

0 44 108 968 3960

0 0 0 0 0

0 76 348 3336 22200
Output

? 00101

? 11001

? 10000

? 11111

! 11001
Note

For the first example, the edge set of the tree secretly held by the judge is $$$(1,3),(2,3),(3,4),(4,5)$$$.

In the first question, $$$S=\{3,5\}$$$.

Note that $$$d(3,3)=0,d(3,5)=d(5,3)=2,d(5,5)=0$$$.

For example, there are the following $$$4$$$ vertex sequences $$$a$$$ of length $$$2$$$ whose elements belong to $$$S$$$.

  • If $$$a=(3,3)$$$, then the score of this sequence is $$$d(3,3) \times d(3,3) = 0 \times 0 = 0$$$
  • If $$$a=(3,5)$$$, then the score of this sequence is $$$d(3,5) \times d(5,3) = 2 \times 2 = 4$$$
  • If $$$a=(5,3)$$$, then the score of this sequence is $$$d(5,3) \times d(3,5) = 2 \times 2 = 4$$$
  • If $$$a=(5,5)$$$, then the score of this sequence is $$$d(5,5) \times d(5,5) = 0 \times 0 = 0$$$

The judge responds with $$$8$$$ for $$$q_2$$$, which is the remainder when $$$0+4+4+0$$$ is divided by $$$2^{61}-1$$$.

By computing similarly for the other sequence lengths, we obtain the judge's response 0 8 0 32 0.

The leaves of this tree are vertices $$$1,2,5$$$, and outputting ! 11001 correctly completes the identification of the leaves.