K. Guess the String
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

The jury's program has a string $$$s$$$ of length $$$n$$$, which consists of the letters 'a', 'b', and 'c'. Your program must guess it.

To guess the string, your program can make queries. Each query has form of a number $$$i$$$ ($$$1 \le i \le n - 1$$$) and a string $$$u$$$ of length two that consisting of lowercase letters of the English alphabet. In response to a query, the jury's program reports how many of the statements $$$s_i = u_1$$$ and $$$s_{i+1}=u_2$$$ are true.

You are required to guess the thought string, making no more than $$$\lceil \frac43 n \rceil$$$ queries. Here $$$\lceil \ldots\rceil$$$ denotes rounding up.

Interaction

In this problem, you will need to play with the jury's program several times. It is guaranteed that the number of games in each run does not exceed $$$100$$$.

At the beginning of each game, your program should read from the standard input stream the number $$$n$$$ ($$$2 \le n \le 100$$$). If $$$n=0$$$, this means that your program should terminate its execution. Otherwise, you start the game with a thought string of length $$$n$$$, and your program can make no more than $$$\lceil \frac43 n \rceil$$$ queries.

To make a query, you need to print to the output stream "? $$$i$$$ $$$u$$$", where $$$1 \le i \le n - 1$$$, $$$u$$$ is a string of two lowercase English letters. In response, you need to read from the standard input stream an integer $$$a$$$, equal to 0, 1, or 2 — how many of the statements from $$$s_i = u_1$$$ and $$$s_{i+1}=u_2$$$ are true.

When your program has guessed the thought string, it is necessary to print to the standard output stream "! $$$s$$$", where $$$s$$$ is the string of length $$$n$$$ that the jury's program has thought of. Printing the answer does not count as a query. After your program prints the guessed string, it can immediately proceed to the next game.

The jury's program in this problem may be adaptive. In other words, the jury's program can tailor its responses in such a way that there exists a string for which all responses are correct, but it is not fixed in advance and changes depending on the queries of your program. In particular, if there is a string for which all responses to queries are correct, but different from the string that your program guessed, the solution may receive a verdict of "Wrong answer".

Example
Input
3

2

1

1

2

0
Output

? 1 ab

? 2 ba

? 2 bb

? 2 bc

! abc
Note

In the example of interactive interaction, queries and responses are separated by empty lines to visually show the interaction process. In the actual interaction with the jury's program, there will be no empty lines, nor should they be printed, but after each query, as well as after printing the answer, it is necessary to print a newline.