CF1117E.Decypher 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.

You are given a string $t$ consisting of $n$ lowercase Latin letters. This string was cyphered as follows: initially, the jury had a string $s$ consisting of $n$ lowercase Latin letters. Then they applied a sequence of no more than $n$ (possibly zero) operations. $i$-th operation is denoted by two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), and means swapping two elements of the string with indices $a_i$ and $b_i$. All operations were done in the order they were placed in the sequence. For example, if $s$ is xyz and $2$ following operations are performed: $a_1 = 1, b_1 = 2$; $a_2 = 2, b_2 = 3$, then after the first operation the current string is yxz, and after the second operation the current string is yzx, so $t$ is yzx.

You are asked to restore the original string $s$. Unfortunately, you have no information about the operations used in the algorithm (you don't even know if there were any operations in the sequence). But you may run the same sequence of operations on any string you want, provided that it contains only lowercase Latin letters and its length is $n$, and get the resulting string after those operations.

Can you guess the original string $s$ asking the testing system to run the sequence of swaps no more than $3$ times?

The string $s$ and the sequence of swaps are fixed in each test; the interactor doesn't try to adapt the test to your solution.

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

你被给定一个由 $n$ 个小写拉丁字母组成的字符串 $t$。该字符串是通过如下方式加密得到的：最初，出题方有一个由 $n$ 个小写拉丁字母组成的字符串 $s$；然后他们执行了一组至多 $n$ 次（可能为零次）的操作。第 $i$ 次操作用两个整数 $a_i$ 和 $b_i$（满足 $1 \le a_i, b_i \le n$）表示，含义是交换字符串中下标为 $a_i$ 和 $b_i$ 的两个字符。所有操作按其在序列中出现的顺序依次执行。例如，若 $s$ 为 xyz，且接下来执行两次操作：$a_1 = 1, b_1 = 2$；$a_2 = 2, b_2 = 3$，则第一次操作后当前字符串变为 yxz，第二次操作后变为 yzx，因此 $t$ 为 yzx。

你需要还原原始字符串 $s$。遗憾的是，你对加密过程中所用的操作序列一无所知（甚至不知道是否存在任何操作）。但你可以任选一个仅含小写拉丁字母、长度为 $n$ 的字符串，并请求评测系统对该字符串执行完全相同的操作序列，从而获得操作后的结果字符串。

你能否仅向评测系统发起至多 3 次询问（即至多 3 次请求执行该交换序列），就推断出原始字符串 $s$？

每个测试用例中的字符串 $s$ 和交换操作序列均为固定值；交互器不会根据你的解法动态调整测试数据。

Initially the testing system sends one string $t$, consisting of lowercase Latin letters ($1 \le |t| = n \le 10^4$).

初始时，评测系统会发送一个字符串 $t$，该字符串由小写拉丁字母组成（$1 \le |t| = n \le 10^4$）。

To give the answer, your program should print one line $!$ $s$ with a line break in the end. After that, it should flush the output and terminate gracefully.

要给出答案，您的程序应打印一行 $!$ $s$，并在末尾换行。之后，程序应刷新输出并正常终止。

In the sample, the testcase described in the statement is used. The participant asks the first query with string baa, which is transformed to aab. The second query contains string aba, which is transformed to baa. The third query contains string aab, which is transformed to aba. The participant can deduce that the initial string $s$ was xyz.

Note for hacking phase:

To submit a test in hacking phase, you should provide it in the following format:

The first line should contain the string $s$ you guess, consisting of $n \in [1, 10000]$ lowercase Latin letters.

The second line should contain $k$ ($0 \le k \le n$) — the number of swap operations in the sequence.

Then $k$ lines should follow, $i$-th of them should denote $i$-th operation with two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$).

For example, the sample test would look like that:

xyz

2

1 2

2 3

在样例中，使用了题目描述中的测试用例。参赛者首先查询字符串 baa，该字符串被变换为 aab；第二次查询的字符串为 aba，被变换为 baa；第三次查询的字符串为 aab，被变换为 aba。参赛者由此可推断出初始字符串 $s$ 为 xyz。

对 Hack 阶段的说明：

在 Hack 阶段提交测试数据时，需按如下格式提供：

第一行应包含你猜测的字符串 $s$，由 $n \in [1, 10000]$ 个小写拉丁字母组成。

第二行应包含 $k$（$0 \le k \le n$）——即交换操作序列的长度。

随后是 $k$ 行，其中第 $i$ 行应表示第 $i$ 次操作，包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$）。

例如，样例测试数据如下所示：

xyz

2

1 2

2 3