곡예 비행 6

Bitaro는 곡예 비행 대회에 참가하여 비행기를 조종한다. 비행기는 일정한 고도를 유지하면서 체크포인트들을 통과한다. 비행 구역은 좌표평면으로 본다. 체크포인트는 $N$개이며 1번부터 $N$번까지 번호가 매겨져 있다. 체크포인트 $i$의 좌표는 $(X_i, Y_i)$이다.

비행은 다음 순서로 진행한다.

1. Bitaro가 시작 체크포인트를 고르면, 비행기는 그 지점에서 출발한다.
2. 아래 과정을 $N-1$번 반복한다. 아직 선택하지 않은 체크포인트 중에서 Bitaro가 다음 체크포인트를 고른다. 비행기는 현재 체크포인트에서 다음 체크포인트까지 직선으로 날아간다.
3. 마지막 체크포인트에 도착하면 비행이 끝난다.

2번 단계에서 시작 체크포인트는 이미 선택된 것으로 본다. 비행기는 직선으로만 날아야 한다. 곡선을 그리거나 비행 도중 방향을 바꾸는 것은 금지된다.

비행 경로는 꺾은선이다. 비행기는 비행 중 방향을 최대 $N-2$번 바꾼다. 꺾은선의 각이 작은 체크포인트에서는 방향 변화가 커서 비행에 실패할 위험이 있다.

Bitaro는 시작 체크포인트와 마지막 체크포인트를 제외한 $N-2$개 체크포인트에서 꺾은선의 최소 각을 가능한 한 크게 만들고자 한다. 체크포인트 좌표가 주어졌을 때, 꺾은선의 최소 각이 최대가 되는 방문 순서를 구하시오.

첫째 줄에 $N$과 $Z_0$이 주어진다. $Z_0$은 채점기가 사용하는 매개변수이다. 둘째 줄부터 $N$개의 줄에 각 체크포인트의 $X_i$와 $Y_i$가 주어진다.

$N$개의 줄을 출력한다. $k$번째 줄에는 비행 경로에서 $k$번째로 지나는 체크포인트 번호 $P_k$ ($1 \le P_k \le N$)를 출력한다. 시작 체크포인트가 $P_1$이다.

• $3 \le N \le 1000$
• $\sqrt{X_i^2 + Y_i^2} \le 10000000$ ($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$