题目描述

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)$ .

输入格式

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.

4

first

second

first

query 2 1

query 2 4

query 1 3

answer 4 2 1 3

提示

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.