Duloc Network#12972

Duloc Network

2 seconds
512 megabytes
Hard

This is an interactive problem, where your program and the judge interact via standard input and output.

In the kingdom of Duloc, Lord Farquaad is developing a network of watchtowers to monitor every corner of his land. He has a map of towers and the roads that connect them, forming an undirected simple graph G=(V,E), where each tower is a vertex and each road is an edge between two towers. However, Farquaad is worried that some parts of Duloc might be isolated, making it impossible to reach every tower from any other.

To ensure full connectivity, he tasks you with verifying whether his network is connected. However, there’s a catch: you’re only allowed limited access to information about the graph.

You can query the network to investigate its connectivity. A query allows you to select a subset of towers and receive a count of the towers not in that have direct roads connecting them to at least one tower in . More precisely, query(S) = |N(S) \setminus S|, where S \subseteq V and N(S) = \{x \vert \exists y \in S \text{ such that } (x, y) \in E\}.

Your goal is to use these queries efficiently to determine if the network is connected.

Can you help Lord Farquaad confirm the security of his kingdom by verifying that every tower is reachable from any other in Duloc’s network?

Input

Interaction starts by reading an integer — the number of vertices.

Then you can make queries of the type "? s" (without quotes) where is a binary string of length such that character s_i is 1 if node i \in S and 0 otherwise. After the query, read an integer — the answer to your query.

After printing a query do not forget to output end of line and flush the output. The interactor is non-adaptive. The graph does not change during the interaction.

1 \leq |V| \leq 200.

You are allowed to use at most 3500 queries.

Output

When you find if is connected or disconnected, print it in the format "! x" (without quotes), where is 1 if is connected and 0 otherwise.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

In the following interaction, |V| = 4, G = (V, E), V = \{1, 2, 3, 4\}, E = \{(1, 2), (2, 3), (3, 4), (2, 4)\}.

Input

Output

Description

4

is given.

? 1100

Ask a query for subset .

2

The judge responds with 2.

? 0010

Ask a query for subset .

2

The judge responds with 2.

? 1001

Ask a query for subset .

2

The judge responds with 2.

! 1

The algorithm detected that G is connected.

Here is another example, |V| = 2, G = (V, E), V = \{1, 2\}, E = \emptyset.

Input

Output

Description

2

is given.

? 10

Ask a query for subset .

0

The judge responds with 0.

? 11

Ask a query for subset .

0

The judge responds with 0.

! 0

The algorithm detected that G is disconnected.