J. Gibberish
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

While roaming through the Swiss Alps one weekend, you stumble upon a curious creature. At first, it appears the creature is speaking Swiss German gibberish. However, after some time, you begin to notice a pattern in its speech!

Whenever you say a word consisting of exactly $$$n$$$ letters, the creature applies a fixed permutation to the letters and says the permuted word back.

More formally, the creature has a hidden permutation $$$p$$$ of size $$$n$$$. When you say a word $$$w_1 w_2 ... w_n$$$, the creature constructs a new word by placing letter $$$w_1$$$ at position $$$p_1$$$, letter $$$w_2$$$ at position $$$p_2$$$, ..., letter $$$w_n$$$ at position $$$p_n$$$, and says the new word back to you.

Your task is to find the permutation $$$p$$$.

Interaction

You should begin by reading a single integer $$$n$$$ ($$$1 \leq n \leq 100~000$$$) – the length of the permutation.

After that, you can print queries of the format "? w", where $$$w$$$ is a string consisting of exactly $$$n$$$ lowercase letters. Don't forget to flush the output after printing a query!

After each query, you should read a string, the result of applying $$$p$$$ to $$$w$$$.

You are allowed to make at most $$$4$$$ queries.

When you have figured out the permutation $$$p$$$, print your guess for $$$p$$$ as "! p1 p2 ... pn" and terminate.

Example
Input
5

hello

wolrd
Output

? hello

? world

! 1 2 4 3 5
Note

To flush the output, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.