Description

Original problem at JOISC 2021 Day1 T1 Aerobatics.

Bitaro will participate in an aerobatics competition. In this competition, Bitaro will fly an airplane. The airplane will keep a certain altitude, and pass through the checkpoints. The area where the airplane will fly is considered as a coordinate plane. There are $N$ checkpoints, numbered from $1$ to $N$. The coordinate of the checkpoint $i$ $(1 \leq i \leq N)$ is $(X_i,~Y_i)$. During the competition, the airplane must pass through each checkpoint once. More precisely, the airplane must fly in the following way.

1. First, Bitaro chooses the starting checkpoint, and the airplane will start flying from there.
2. Repeat the following $N − 1$ times. Among the checkpoints which are not yet chosen, Bitaro chooses a checkpoint as the next checkpoint. Then the airplane will fly straight from the current checkpoint to the next checkpoint.
3. When the airplane arrived at the last checkpoint, the flight is finished. Here, in the step 2, we consider the starting checkpoint as an already chosen checkpoint.

The airplane must fly straight from a checkpoint to the next checkpoint. It is forbidden to draw a curve or make a turn on the way.

The route of the airplane is a polygonal line. During the flight, the airplane will change its direction at most $N−2$ times. If the angle of the polygonal line at a checkpoint is small, the change of the direction of the airplane at that checkpoint is large, and there is a risk of failure of the flight.

Therefore, Bitaro wants to make the minimum angle of the polygonal line at the $N − 2$ checkpoints, except for the starting checkpoint and the last checkpoint, as large as possible.

Given the coordinates of the checkpoints, find an order of the checkpoints to pass so that the minimum angle of the polygonal line is as large as possible.

Input Format

The first line consists two integers $N$ and $Z_0$, where $Z_0$ is a parameter used by the grader.

In the following $N$ lines, there are two integers $X_i$ and $N_i$ each line.

Output Format

The output should consist of $N$ lines. The $k$-th line $(1 \leq k \leq N)$ of the output should contain the integer $P_k (1 \leq P_k \leq N)$, which is the $k$-th checkpoint in the route of the airplane. Here, the starting checkpoint is the first checkpoint $P_1$.

Submission

Submit output data output output_01.txt, output_02.txt, ..., output_06.txt for each of the input files input_01.txt, input_02.txt, ..., input_06.txt.

Constraints

For all test data, it is guaranteed that,

• $3 \le N \le 1\,000$。

• $\sqrt{X_i^2+Y_i^2} \le 10\,000\,000\ (1 \le i \le N)$。

• $(X_i,Y_i) \ne (X_j,Y_j)\ (1 \le i < j \le N)$。

• $1 \le Z_0 \le 179$。

Library

Library In this task, you can use a library which contains a function calculating an angle determined by three points. The library is contained in the file aerobatics.h in the archive. The specification is as follows.

• double GetAngle(int xa, int ya, int xb, int yb, int xc, int yc)
  This function calculates the angle $\mathrm{BAC}$ in degree. It returns a real number with sufficiently small error. Make sure the order of the parameters.
  • Concerning the point $A$, the parameter xa is the $x$-coordinate of the point $A$, and the parameter ya is the $y$-coordinate of the point $A$.
  • Concerning the point $B$, the parameter xb is the $x$-coordinate of the point $B$, and the parameter yb is the $y$-coordinate of the point $B$.
  • Concerning the point $C$, the parameter xc is the $x$-coordinate of the point $C$, and the parameter yc is the $y$-coordinate of the point $C$.
  • If the coordinates of the points $A,~B$ are the same or the coordinates of the points $A,~C$ are the same, the behavior of this function is undefined.

In your program calculating the solutions of this task, you may use the function GetAngle in the library. If you use it, you may modify the function.

The GetAngle is the same as the function used by the grader.

Grading

For each output data, your score is calculated in the following way.

If your output is incorrect, your score is $0$. For example, if the output sequence $P_1, P_2, \ldots , P_N$ is not permutation of $1, 2, \ldots, N$ or the format of the output is incorrect, your score is $0$.

If your output is correct, your score is calculated as follows. Let $Z$ (degree) be the minimum angle of the polygonal line at the $N − 2$ checkpoints, except for the starting checkpoint and the last checkpoint. Then your score $S$ is calculated by the following formula.

• If $Z\geq Z_0$, your score is $S$.
• If $Z<Z_0$$, your score is$S \times \dfrac{f(Z/180)}{f(Z_0/180)}$

Here function $f(\alpha)~(0\leq\alpha 1)$ is defined by $f(\alpha)=4\alpha^4+\alpha$.

Your score for this task is the sum of your scores for the 6 input data, rounded to the nearest integer. For each input data, the values of $N, Z_0$ and the score are given in the following table.

7 90
3 1
2 5
0 2
-1 6
-3 1
-1 -4
4 -2

5
3
1
7
6
4
2