Problem F
Crack the Password

Disaster! The programming olympiad final has started, but you’ve forgotten the login to your computer. Luckily, you’re not a sheep following the flock. You refuse to use Windows and instead use Progolymp-OS. If you forget your password in this operating system, you receive clues when you make a guess. More specifically, assume that the password is $P$, and you guess $G$. The system will respond with

where $LCS(G,P)$ is the length of the longest common subsequence of $G$ and $P$. The longest common subsequence of two strings $G$ and $P$ is defined as follows: let’s denote all subsequences of a string $S$ by the set of all strings that can be obtained by removing zero or more letters from $S$ while maintaining the relative order of the remaining letters. $LCS(G,P)$ is the length of the longest string that appears in both the subsequences of $G$ and $P$.

For example: if $P=$”abc”, its subsequences are {””, ”a”, ”b”, ”c”, ”ab”, ”ac”, ”bc”, ”abc”}. If $G=$”ac”, its subsequences are {””, ”a”, ”c”, ”ac”}. The longest common subsequence is ”ac”, and thus $LCS(G,P)=2$.

A few more examples: the longest common subsequence of ”aggtab” and ”gxtxayb” is ”gtab”. Therefore, $LCS($”aggtab”, ”gxtxayb”$) = 4$. Two more examples are $LCS($”abc”, ”cba”$) = 1$ and $LCS($”po”, ”trakigt”$) = 0$.

You can now make up to 10,000 guesses before the system locks up. Each guess consists of giving your computer $G$, and it responds with $LCS(G,P)$. Additionally, you want to use as few guesses as possible so you can get back into the competition as soon as possible.

Interaction

Your program should first read two integers $N$ and $K$ ($1 \leq N \leq 100$, $1 \leq K \leq 26$): the number of letters in the password and how many unique letters it can contain. More specifically, the password $P$ consists of exactly $N$ letters chosen from the first $K$ lowercase letters of the alphabet.

To make a guess, you should print a line in the format ? G. $G$ must satisfy $1 \le |G| \le N$ and only contain letters from the first $K$ lowercase letters of the alphabet. ($1 \le |G| \le N$), The program will then read an integer, $LCS(G,P)$.

When making your final guess, print a line with the character !, followed by a string of length $N$, your guess of the password. After this, your program should terminate and no more output should be written. This final guess does not count toward the limit of 10,000 guesses.

It is guaranteed that the string $P$ in each test case is determined in advance and does not change adaptively in response to your measurements. There are no guarantees on $P$ such as it being a real word or anything like that, as it is a strong password.

Make sure to flush the output after every print statement, otherwise you may get a Time Limit Exceeded. In C++, this can be done for example with cout << flush; or fflush(stdout);, in Python this is done automatically when you use input(), but otherwise you need to use sys.stdout.flush(), and in Java with System.out.flush();.

Scoring

Your solution will be tested on a number of test case groups. If you fail to find the password in any test case, you will receive zero points for the group it belongs to. Otherwise, let $g$ be the largest number of guesses you used to find the passwords in a certain test case group. If the group is worth $P$ points, you will get

points for that group. You will receive 100 points for the entire problem if you never use more than 666 guesses for a test case.

The table below shows the value of $\frac{666}{g}$ rounded down for different numbers of guesses.

For the following test case groups:

Explanation of Sample 1

The secret password is bbacba. Note that the interaction does not show a reasonable strategy, but only demonstrates the format.

6 3

? ab

2

? bacb

4

? babb

3

! bbacba