There are points numbered through on a two-dimensional plane. Point () has coordinates . Let be the maximum distance between two points.
For a permutation of , define the length of the tour represented by this permutation as follows. Here, .
Choose the permutation so that is small. See the Scoring section for details.
The input is given from Standard Input in the following format:
For each test case, print a permutation of on one line.
For each test case in a subtask, compute the following value.
Each case is given in the following format:
If there are multiple solutions, print any of them.
Let be the largest value of among all test cases in that subtask.
The score for Subtask is determined as follows.
Condition | Score |
|---|---|
The score for Subtask is determined as follows.
Condition | Score |
|---|---|