GANNHAT  Closest distance
English  Vietnamese 
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).
Input
 The first line contains a positive integer N (1 ≤ N ≤ 200000).
 The ith line of the next N lines contains two integers x and y which are coordinates of the ith point(0 ≤ x, y ≤ 10^{7})
Output
 Print N lines, in which the ith line contains the minimum distance for the ith point.
Example
Input: 4 0 0 0 1 1 0 1 1 Output: 1 1 1 1
hide comments
Harsh Gupta:
20151207 09:33:49
Time limit is very strict.


Pagan Min:
20150519 05:21:17
any hints for the problem...cant get a start 

aristofanis:
20140317 19:33:45
For those who don't like this sample test case (like @c0d3junki3 below), here is an other one:


Dragan MarkoviĆ¦:
20130801 12:22:00
Worst sample case ever.


Nic Roets:
20121125 09:49:08
@Khanh There is no test for that (I got AC and my output for N=1 is random.) Last edit: 20121125 09:49:34 

karan173:
20120930 23:01:20
hey please increase time limit for java as there are no currently accepted solutions 

Khanh Quynh:
20090414 17:10:31
If N=1 what's the result? 
Added by:  Kaiel 
Date:  20080502 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  CPP JAVA PASGPC PASFPC 
Resource:  Mr Taek 