SP2678 GANNHAT - Closest distance

[English](/problems/GANNHAT/en/) [Vietnamese](/problems/GANNHAT/vn/)The manhattan distance between two points A(x $ _{1} $ ,y $ _{1} $ ) and B(x $ _{2} $ ,y $ _{2} $ ) is defined as following: D(A,B) = |x $ _{1} $ - x $ _{2} $ | + |y $ _{1} $ - y $ _{2} $ | Given N points A $ _{1} $ , A $ _{2} $ , ..., A $ _{N} $ , for each point A $ _{i} $ you need to calculate the minimum D(A $ _{i} $ , A $ _{j} $ ) (j ≠ i).

- 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 $ ^{7} $ )

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