Khoảng cách Manhattan giữa 2 điểm A(x₁,y₁) và B(x₂,y₂) được định nghĩa như sau:

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

Cho N điểm A₁, A₂, ..., A_N trên mặt phẳng, với mỗi điểm A_i ta cần tìm D(A_i , A_j) nhỏ nhất với j ≠ i.

Dữ liệu

• Dòng đầu ghi số nguyên dương N (1 ≤ N ≤ 200000).
• N dòng sau dòng thứ i ghi 2 số x và y là tọa độ của điểm thứ i. (0 ≤ x , y ≤ 10⁷)

Kết quả

• Gồm N dòng, dòng thứ i ghi khoảng cách nhỏ nhất cần tìm đối với điểm thứ i.

Ví dụ

Dữ liệu:
4
0 0
0 1
1 0
1 1

Kết quả:
1
1
1
1