CF2206A.Compare Suffixes

The judge program possesses a hidden string $S$ of length $n$ consisting only of lowercase Latin letters (a–z). You cannot access the string. At the start, only the length $n$ is given to you.

Your task is to determine the order of all $n$ suffixes using a limited number of queries.

For an integer $k$ ($1 \le k \le n$), let $S(k)$ denote the suffix of $S$ starting at the $k$-th character. In particular, $S(1)=S$.

In a single query, you specify two distinct integers $i$ and $j$. The judge program compares $S(i)$ and $S(j)$ lexicographically and returns whether $S(i) \lt S(j)$ or $S(i) \gt S(j)$ to you. Note that ties never occur for $i\not= j$ because all suffixes are distinct.

Find a permutation $(p_1,p_2,\ldots,p_n)$ of $(1,2,\ldots,n)$ such that $S(p_1) \lt S(p_2) \lt \cdots \lt S(p_n)$.

Interaction

The first line of input contains the integer $n$ ($2 \le n \le 1000$).

To issue a query, your program should write a line of the form "query $i$ $j$" ($1 \le i \le n; 1 \le j \le n; i \not= j$). After that, an input line containing first or second becomes available. A line containing first means $S(i) \lt S(j)$, while a line containing second means $S(i) \gt S(j)$.

Once you determine the order of the suffixes, your program should write a line of the form "answer $p_1$ $p_2$ $\ldots$ $p_n$". After that, the interaction stops and your program should terminate without extra output.

Your program may issue at most $6260$ queries. If your program issues more than $6260$ queries, it will be judged as "Wrong Answer."

It is guaranteed that the hidden string $S$ consists only of lowercase letters (a–z).

Notes on interactive judging:

• The evaluation is non-adversarial, meaning that the string $S$ is chosen in advance rather than in response to your queries.
• Do not forget to flush output buffers after writing.
• You are provided with a command-line tool for local testing, together with input files corresponding to the sample interactions. You can download these files. The tool has comments at the top to explain its use.

评测程序持有一个长度为 $n$ 的隐藏字符串 $S$，该字符串仅由小写拉丁字母（a–z）组成。你无法直接访问该字符串。初始时，你仅获知其长度 $n$。

你的任务是通过有限次数的查询，确定该字符串全部 $n$ 个后缀的字典序排列顺序。

对整数 $k$（$1 \le k \le n$），记 $S(k)$ 表示从第 $k$ 个字符开始的 $S$ 的后缀。特别地，$S(1) = S$。

在一次查询中，你需要指定两个互异的整数 $i$ 和 $j$。评测程序将对 $S(i)$ 与 $S(j)$ 进行字典序比较，并向你返回 $S(i) \lt S(j)$ 或 $S(i) \gt S(j)$。注意：由于所有后缀互不相同，当 $i \ne j$ 时，不会出现相等的情况。

请找出一个 $(1,2,\ldots,n)$ 的排列 $(p_1,p_2,\ldots,p_n)$，使得 $S(p_1) \lt S(p_2) \lt \cdots \lt S(p_n)$。

交互方式

输入的第一行包含整数 $n$（$2 \le n \le 1000$）。

要发起一次查询，你的程序应输出一行，格式为 "query $i$ $j$"（其中 $1 \le i \le n$，$1 \le j \le n$，且 $i \ne j$）。随后，将有一行输入可用，内容为 first 或 second：若为 first，表示 $S(i) \lt S(j)$；若为 second，表示 $S(i) \gt S(j)$。

一旦你确定了所有后缀的排序顺序，你的程序应输出一行，格式为 "answer $p_1$ $p_2$ $\ldots$ $p_n$"。此后交互结束，你的程序应立即终止，不得输出额外内容。

你的程序最多可发出 $6260$ 次查询。若查询次数超过 $6260$，将被判为“答案错误”。

保证隐藏字符串 $S$ 仅由小写字母（a–z）组成。

关于交互式评测的注意事项：

• 评测是非对抗性的，即字符串 $S$ 是预先选定的，而非根据你的查询动态生成。
• 输出后务必刷新输出缓冲区。
• 我们为你提供了一个命令行本地测试工具，以及对应样例交互的输入文件。你可以下载这些文件。该工具顶部附有注释，说明其使用方法。

Explanation for the sample interaction #1

In this sample, $S=\texttt{icpc}$ is assumed. The order of four suffixes is $S(4) \lt S(2) \lt S(1) \lt S(3)$ because $\texttt{c} \lt \texttt{cpc} \lt \texttt{icpc} \lt \texttt{pc}$.

In the first and third query, first is returned because $S(2) \lt S(1)$ and $S(1) \lt S(3)$. In the second query, second is returned because $S(2) \gt S(4)$. With these responses, you can determine the ordering.

样例交互 #1 的说明

在本样例中，假设 $S=\texttt{icpc}$。四个后缀的顺序为 $S(4) \lt S(2) \lt S(1) \lt S(3)$，这是因为 $\texttt{c} \lt \texttt{cpc} \lt \texttt{icpc} \lt \texttt{pc}$。

在第一次和第三次查询中，返回 first，因为 $S(2) \lt S(1)$ 且 $S(1) \lt S(3)$；在第二次查询中，返回 second，因为 $S(2) \gt S(4)$。通过这些响应，你可以确定全部后缀的顺序。