시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 2 2 28.571%

문제

두 점 A(x1, y1)와 B(x2, y2) 사이의 거리 D(A, B)는 다음과 같이 구한다.

D(A, B) = |x1 - x2| + |y1 - y2|

점 N개 A1, A2, ..., AN이 주어졌을 때, 각각의 점 Ai마다 가장 가까운 점 Aj와의 거리 D(Ai, Aj) (i ≠ j)를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에는 점 Ai의 좌표 x와 y가 주어진다. (-10,000,000 ≤ x, y ≤ 10,000,000)

출력

각각의 점 Ai마다 가장 가까운 점과의 거리를 출력한다. A1부터 AN까지 순서대로 한 줄에 하나씩 출력한다.

예제 입력

4
0 0
0 1
1 0
1 1

예제 출력

1
1
1
1

예제 입력 2

4
0 0
1 100
4 3
100 2

예제 출력 2

7
100
7
97

예제 입력 3

4
0 0
3 3
1 100
100 1

예제 출력 3

6
6
99
99

힌트

출처