트릭 오어 트릿!

할로윈에 아이들이 분장을 하고 사탕을 모으러 집집마다 돌아다니는 것은 흔한 놀이다. 그런데 올해는 문제가 생겨서 거리에 아이가 너무 많이 나왔고, 모든 아이에게 사탕이 돌아가지 않을 수도 있다.

그래서 아이들은 사탕을 더 많이 얻으려고 무리를 짓기로 했다. 하지만 미리 조율할 시간이 없어서, 각 아이는 자신과 가장 가까운 다른 아이를 향해 가기로 했다. 물론 이것이 최선의 전략은 아니다. 예를 들어 아이 A가 B를 향해 가는 동안 B는 이미 C를 향해 출발했을 수도 있다. 그래도 몇몇 무리는 만들어지기를 바랄 뿐이다...

맨해튼 거리에 $n$명의 아이가 나왔고, $i$번째 아이는 좌표 $(x_i, y_i)$의 점에 있다. 두 점 $(x_i, y_i)$와 $(x_j, y_j)$ 사이의 맨해튼 거리는 $|x_i - x_j| + |y_i - y_j|$이다.

도로가 혼잡해지지 않도록, 각 아이에 대해 자신과 가장 가까운 다른 아이의 번호를 구하라. 아이들이 도시에서 움직일 경로를 대략적으로라도 예측할 수 있어야 하기 때문이다.

첫 줄에 도시에 있는 아이의 수 $n$이 주어진다 ($2 \leq n \leq 10^5$).

이어지는 $n$개의 줄에는 $i$번째 아이의 좌표 $x_i$와 $y_i$가 공백으로 구분되어 주어진다 ($0 \leq x_i, y_i \leq 10^9$).

모든 아이가 서로 다른 점에 있다고 보장되지 않는다. 두 아이의 좌표가 같다면, 두 아이 모두에게 최단 거리는 $0$이다.

$1$부터 $n$까지의 정수 $n$개를 공백으로 구분해 출력하라. $i$번째 수는 맨해튼 거리 기준으로 $i$번째 아이에게 가장 가까운 아이의 번호이다.