The manhattan distance between two points A(x₁,y₁) and B(x₂,y₂) is defined as following:

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

Given N points A₁, A₂, ..., A_N, for each point A_i you need to calculate the minimum D(A_i , A_j) (j ≠ i).

Input

• The first line contains a positive integer N (1 ≤ N ≤ 200000).
• The i-th line of the next N lines contains two integers x and y which are co-ordinates of the i-th point(0 ≤ x, y ≤ 10⁷)

Output

• Print N lines, in which the i-th line contains the minimum distance for the i-th point.

Example

Input:
4
0 0
0 1
1 0
1 1

Output:
1
1
1
1