题目描述

You want to sort $\mathbf{N}$ distinct items, $x_1$, $x_2$, $\ldots$, $x_{\mathbf{N}}$. Unfortunately, you do not have a way of comparing two of these items. You only have a way to, given three of them, find out which one is the median, that is, which one is neither the minimum nor the maximum among the three.

For example, suppose $\mathbf{N} = 5$ and you know that:

• $x_1$ is the median of $\{x_1, x_2, x_3\}$
• $x_2$ is the median of $\{x_2, x_3, x_4\}$
• $x_3$ is the median of $\{x_3, x_4, x_5\}$

Then, it is guaranteed that the sorted order of the elements is either $x_4, x_2, x_1, x_3, x_5$ or its reverse $x_5, x_3, x_1, x_2, x_4$. Notice that by knowing only medians, it is impossible to distinguish the order of any list from its reverse, since the median question has the same result for any three elements in both cases.

Your program will have to find the order of $\mathbf{T}$ lists of $\mathbf{N}$ elements using at most $\mathbf{Q}$ median questions in total (or $\mathbf{Q}/\mathbf{T}$ queries per list on average). In each case, finding either the right order or its reverse is considered correct. The order for each case is generated uniformly at random from all possible orders, and independently of any other information.

Interactive Protocol

This is an interactive problem.

Initially, the judge will send you a single line containing three integers $\mathbf{T}$, $\mathbf{N}$, and $\mathbf{Q}$: the number of test cases, the number of elements to sort within each test case, and the total number of questions you are allowed across all test cases, respectively. Then, you must process $\mathbf{T}$ test cases. Each test case consists of a series of question exchanges plus an additional exchange to provide the answer.

For a question exchange, your program must print a single line containing three distinct integers $i$, $j$, $k$ all between 1 and $\mathbf{N}$, inclusive, which corresponds to asking the judge "which element is the median of the set $\{x_i, x_j, x_k\}$?" The judge will respond with a single line containing a single integer $\mathbf{L}$, meaning that the median of that set is $x_{\mathbf{L}}$ ($\mathbf{L}$ is always equal to one of $i$, $j$, or $k$). If you try to perform a $(\mathbf{Q} + 1)$-th question exchange, the judge will simply output -1.

Once you are ready to state the result, print a line containing $\mathbf{N}$ integers representing the indices of the elements in sorted or reverse sorted order. The judge will respond with a single integer 1 if your answer is correct or -1 if it is not. After receiving the judge's answer for the $\mathbf{T}$-th case, your program must finish in time in order to not receive a Time Limit Exceeded error. In addition, if you print additional information after receiving the result for the $\mathbf{T}$-th case, you will get a Wrong Answer judgment.

If the judge receives an invalidly formatted line or invalid values from your program at any moment, the judge will print a single number -1. After the judge prints -1 for any of the reasons explained above, it will not print any further output. If your program continues to wait for the judge after receiving a -1, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

输入格式

See Interactive Protocol.

输出格式

See Interactive Protocol.

2 5 600

2

3

4

1

3

4

5

1

1 2 3

4 2 3

5 4 3

5 4 3 2 1

1 2 3

2 3 4

3 4 5

1 3 5 4 2

提示

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently.

Limits

• $\mathbf{T} = 100$.

Test Set 1 (7 Pts, Visible Verdict)

• $\mathbf{N} = 10$.
• $\mathbf{Q} = 300 \cdot \mathbf{T}$.

Test Set 2 (11 Pts, Visible Verdict)

• $\mathbf{N} = 50$.
• $\mathbf{Q} = 300 \cdot \mathbf{T}$.

Test Set 3 (10 Pts, Hidden Verdict)

• $\mathbf{N} = 50$.
• $\mathbf{Q} = 170 \cdot \mathbf{T}$.