Guess The String
Contest: Educational Codeforces Round 130 (Rated for Div. 2)
Difficulty rating: 1900
Tags: binary search, constructive algorithms, interactive

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: https://codeforces.com/blog/entry/45307.

The jury has chosen a string $$$s$$$ consisting of $$$n$$$ characters; each character of $$$s$$$ is a lowercase Latin letter. Your task is to guess this string; initially, you know only its length.

You may ask queries of two types:

- $$$1$$$ $$$i$$$ — the query of the first type, where $$$i$$$ is an integer from $$$1$$$ to $$$n$$$. In response to this query, the jury will tell you the character $$$s_i$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ — the query of the second type, where $$$l$$$ and $$$r$$$ are integers such that $$$1 \le l \le r \le n$$$. In response to this query, the jury will tell you the number of different characters among $$$s_l, s_{l+1}, \dots, s_r$$$.

You are allowed to ask no more than $$$26$$$ queries of the first type, and no more than $$$6000$$$ queries of the second type. Your task is to restore the string $$$s$$$.

For each test in this problem, the string $$$s$$$ is fixed beforehand, and will be the same for every submission.

Input format:
Initially, the jury program sends one integer $$$n$$$ on a separate line — the size of $$$s$$$ ($$$1 \le n \le 1000$$$).

Output format:
To give the answer, print one line ! s with a line break in the end, where $$$s$$$ should be the string picked by the jury. After that, your program should flush the output and terminate gracefully.

Interaction format:
To ask a query, you should send one line containing the query, in one of the following formats:

- ? 1 i — for a query of the first type ($$$1 \le i \le n$$$);
- ? 2 l r — for a query of the second type ($$$1 \le l \le r \le n$$$).

Don't forget to flush the output after sending the query line.

The answer to your query will be given on a separate line. For a query of the first type, the answer will be the character $$$s_i$$$. For a query of the second type, the answer will be an integer equal to the number of different characters among $$$s_l, s_{l+1}, \dots, s_r$$$.

You are allowed to ask no more than $$$26$$$ queries of the first type, and no more than $$$6000$$$ queries of the second type.

In case you ask too many queries, or the jury program fails to recognize your query format, the answer to your query will be one integer $$$0$$$. After receiving $$$0$$$ as the answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer".

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Let's analyze the example of interaction.

The string chosen by the jury is guess, so initially the jury sends one integer $$$5$$$.

1. the first query is ? 2 1 5, which means "count the number of different characters among $$$s_1, s_2, \dots, s_5$$$". The answer to it is $$$4$$$.
2. the second query is ? 1 2, which means "tell which character is $$$s_2$$$". The answer to it is u.
3. the third query is ? 2 1 2, which means "count the number of different characters among $$$s_1$$$ and $$$s_2$$$". The answer to it is $$$2$$$.
4. the fourth query is ? 1 1, which means "tell which character is $$$s_1$$$". The answer to it is g.
5. the fifth query is ? 1 3, which means "tell which character is $$$s_3$$$". The answer to it is e.
6. the sixth query is ? 1 4, which means "tell which character is $$$s_4$$$". The answer to it is s.
7. the seventh query is ? 2 4 5, which means "count the number of different characters among $$$s_4$$$ and $$$s_5$$$". The answer to it is $$$1$$$, so it's possible to deduce that $$$s_4$$$ is the same as $$$s_5$$$.

In the end, the answer is submitted as ! guess, and it is deduced correctly.

Example input:
5
4
u
2
g
e
s
1

Example output:
? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess

Editorial:
There are several ways to solve this problem. The model solution does it as follows:
Restore the characters of $$$s$$$ from left to right. The first character is restored by query ? 1 1. For each of the next characters, let's ask if this character is new (by querying ? 2 1 i and comparing the result with the number of different characters on the segment $$$[1, i-1]$$$). If it's new, ask ? 1 i to obtain the $$$i$$$-th character (there will be at most $$$26$$$ such queries).
Otherwise, we can find the previous occurrence of the $$$i$$$-th character with binary search. Let $$$f(x,y)$$$ be the number of different characters from position $$$x$$$ to position $$$y$$$. If we want to find the previous occurrence of the $$$i$$$-th character, we need to find the last index $$$j$$$ such that $$$f(j,i) = f(j,i-1)$$$. Since the value $$$f(j,i) - f(j,i-1)$$$ does not decrease when we increase $$$j$$$, we can find the last $$$j$$$ such that $$$f(j,i) - f(j,i-1) = 0$$$, with binary search.
Unfortunately, the number of queries of type $$$2$$$ will be too large if we just use binary search over the whole segment $$$[1,i-1]$$$. To decrease the number of queries, we can use the fact that the value of $$$j$$$ we are interested in is the last occurrence of some character we already met; there are at most $$$26$$$ such values, and binary search among them will need only $$$5$$$ iterations.