Aerobatics 2

Bitaro will take part in an aerobatics competition and fly an airplane. The airplane keeps a fixed altitude and passes through checkpoints on a coordinate plane. There are $N$ checkpoints, numbered 1 to $N$. Checkpoint $i$ ($1 \le i \le N$) is at $(X_i, Y_i)$.

The airplane must pass each checkpoint exactly once, as follows.

1. Bitaro chooses the starting checkpoint. The airplane starts flying from there.
2. Repeat the following $N-1$ times. Bitaro chooses the next checkpoint from those not yet chosen, and the airplane flies straight from the current checkpoint to it.
3. When the airplane reaches the last checkpoint, the flight ends.

In step 2, the starting checkpoint counts as already chosen. The airplane must fly straight from one checkpoint to the next. It may not draw a curve or turn partway along a segment.

The route is a polygonal line. The airplane changes direction at most $N-2$ times. If the angle of the route at a checkpoint is small, the direction change there is large, which risks failing the flight.

Bitaro wants the minimum angle of the route at the $N-2$ checkpoints other than the starting and last checkpoints to be as large as possible. Given the coordinates, find a visiting order that maximizes this minimum angle.

The first line contains $N$ and $Z_0$.

$N Z_0$

$X_1 Y_1$

$\vdots$

$X_N Y_N$

Each of the next $N$ lines contains the coordinates $X_i$ and $Y_i$ of one checkpoint, separated by a space. $Z_0$ is a parameter used by the grader.

Print $N$ lines. The $k$-th line contains $P_k$ ($1 \le P_k \le N$), the number of the $k$-th checkpoint on the route. The starting checkpoint is $P_1$.

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