두 점 A(x₁, y₁)와 B(x₂, y₂) 사이의 거리 D(A, B)는 다음과 같이 구한다.</p>

D(A, B) = |x₁ - x₂| + |y₁ - y₂|

점 N개 A₁, A₂, ..., A_N이 주어졌을 때, 각각의 점 A_i마다 가장 가까운 점 A_j와의 거리 D(A_i, A_j) (i ≠ j)를 구하는 프로그램을 작성하시오.

입력 형식

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

출력 형식

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

예제 입력 1

4
0 0
0 1
1 0
1 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