Dr Tony Zamboni is a renowned physician, especially well-versed in microbiology. However, due to some unfortunate events during his experiments, Dr Zamboni has lost his hearing and voice, and his vision has been reduced to monochromacy: he can distinguish only two colours.

Prior to the accident, Dr Zamboni was working on a miracle medicine. He was sequencing ~n~ molecules, labelled ~1~ through ~n~, and was testing different permutations in an attempt to create a vaccine that would allow programmers to properly read every problem statement on their first try, and never encounter issues such as integer overflow.

Just before his machine exploded, he discovered the correct permutation!

Dr Zamboni knows this permutation ~P_1,P_2,\ldots,P_n~ (i.e. a particular arrangement of the unique values ~1~ through ~n~), but you do not.

Due to his condition, you can communicate with him only in the following way:

For each query, you assign each molecule either black or white. In other words, for every molecule ~i~, you choose a colour ~b_i\in{0,1}~.

Dr Zamboni then rearranges the molecules in the order of his hidden permutation and clicks his tongue once for every pair of consecutive molecules whose assigned colours are different.

Thus, for a query ~b_1,b_2,\ldots,b_n~, his response is \[ \left\lvert \left\lbrace i \mid 1 \le i < n,\ b_{P_i} \ne b_{P_{i+1}} \right\rbrace \right\rvert. \]

Using only these queries, determine the hidden permutation before Dr Zamboni falls asleep.

Interaction

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your program and writes to its standard input. The interaction must follow the format below:

The interactor first sends one integer ~n~ ~(2 \leq n \leq 1000)~, the number of molecules in the vaccine.

You may present Dr Zamboni with up to ~25,000~ queries to determine information about the true molecular permutation before he falls asleep. To conduct a query, print a line in the form ~\texttt{?}\ b_1\dots b_n~. Each ~b_i~ should be either ~0~ or ~1~, and represents the colour you assign the ~i~th molecule. The interactor will respond with a single integer, representing the number of adjacent pairs that have different colours when your molecules are arranged in the order of Dr Zamboni's permutation.

Once you have determined the true molecular permutation of the vaccine, print a line in the form ~\texttt{!}\ P_1\ \dots\ P_n~, ~n~ space-separated values, where each value ~1~ to ~n~ appears uniquely. Note that this interaction cannot distinguish between a permutation and its reverse, so either orientation will be accepted.

You will receive a Wrong Answer if:

• You conduct more than ~25,000~ queries, as Dr Zamboni will fall asleep, or
• You send data that is invalid, or
• Your final answer is wrong.

After printing each line, you must flush stdout. Failure to do so may result in an Idleness Limit Exceeded verdict.

For C++, you may use cout << endl to output, or call cout.flush() after each output.

For Python, use flush=True in print(), or call sys.stdout.flush() after each output.

Example

Interaction 1

5
? 00000
0
? 10000
1
? 11000
3
? 10101
2
? 00010
2
! 1 4 2 5 3

The secret permutation in this example is ~[1,4,2,5,3]~.

One way to view each query is as assigning a binary value to each molecule ~1,2,\dots,n~. Dr Zamboni then reads these values in the order of the secret permutation and returns the number of times the value changes between consecutive positions.

For example, with secret permutation ~[1,4,2,5,3]~, the query 10101 becomes 10011. This sequence changes colour twice, so the response is ~2~. Using this approach, we will analyse each query as follows:

• ? 00000 → 00000: no colour changes, so the response is ~0~.
• ? 10000 → 10000: one colour change, so the response is ~1~.
• ? 11000 → 10100: three colour changes, so the response is ~3~.
• ? 10101 → 10011: two colour changes, so the response is ~2~.
• ? 00010 → 01000: two colour changes, so the response is ~2~.