CF1697D.Guess The String

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.

这是一个交互式问题。在与评测程序通信时，请务必刷新你的输出。你可以在 C++ 中使用 fflush(stdout)，Java 中使用 system.out.flush()，Python 中使用 stdout.flush()，Pascal 中使用 flush(output) 来刷新输出。如果你使用其他编程语言，请查阅其文档。你也可以参考交互式问题指南：https://codeforces.com/blog/entry/45307。

出题人预先选定一个长度为 $n$ 的字符串 $s$；$s$ 中的每个字符均为小写拉丁字母。你的任务是猜出该字符串；初始时你仅知道其长度。

你可以提出两类查询：

• $1$ $i$ —— 第一类查询，其中 $i$ 是 $1$ 到 $n$ 之间的整数。对于该查询，出题人将告诉你字符 $s_i$；
• $2$ $l$ $r$ —— 第二类查询，其中 $l$ 和 $r$ 是满足 $1 \le l \le r \le n$ 的整数。对于该查询，出题人将告诉你子串 $s_l, s_{l+1}, \dots, s_r$ 中不同字符的个数。

你最多可进行 $26$ 次第一类查询，以及最多 $6000$ 次第二类查询。你的任务是还原字符串 $s$。

本题中，对每个测试用例，字符串 $s$ 在开始前即已固定，并且对所有提交均保持不变。

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

最初，评测程序会在单独一行发送一个整数 $n$ —— 字符串 $s$ 的长度（$1 \le n \le 1000$）。

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.

要给出答案，请输出一行 ! s，并在末尾换行，其中 $s$ 应为评测组选定的字符串。之后，你的程序应刷新输出并正常终止。

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.

我们来分析一下交互示例。

评委会选定的字符串是 guess，因此初始时评委会发送一个整数 $5$。

1. 第一个查询是 ? 2 1 5，其含义为：“统计 $s_1, s_2, \dots, s_5$ 中不同字符的个数”。该查询的答案为 $4$。
2. 第二个查询是 ? 1 2，其含义为：“告知 $s_2$ 是哪个字符”。该查询的答案为 u。
3. 第三个查询是 ? 2 1 2，其含义为：“统计 $s_1$ 和 $s_2$ 中不同字符的个数”。该查询的答案为 $2$。
4. 第四个查询是 ? 1 1，其含义为：“告知 $s_1$ 是哪个字符”。该查询的答案为 g。
5. 第五个查询是 ? 1 3，其含义为：“告知 $s_3$ 是哪个字符”。该查询的答案为 e。
6. 第六个查询是 ? 1 4，其含义为：“告知 $s_4$ 是哪个字符”。该查询的答案为 s。
7. 第七个查询是 ? 2 4 5，其含义为：“统计 $s_4$ 和 $s_5$ 中不同字符的个数”。该查询的答案为 $1$，因此可推断出 $s_4$ 与 $s_5$ 相同。

最后，提交答案 ! guess，且推断正确。