MLE - Memory Limit Exceeded

Given n points on X-Y plane. To each point, you are to find the other point who is closest to it with respect to the Euclidean distance.

Input

T (≤ 15) test cases. Each starts with an integer n (2 ≤ n ≤ 100000). Then n lines follow. Each contains two space-separated integers, the X and Y coordinate of the corresponding point, respectively. No two points in one test case will coincide.

Output

For each test case, output n lines. The i-th of them should contain the squared distance between the i-th point from the input and its nearest neighbour.

Example

Input:
2
10
17 41
0 34
24 19
8 28
14 12
45 5
27 31
41 11
42 45
36 27
15
0 0
1 2
2 3
3 2
4 0
8 4
7 4
6 3
6 1
8 0
11 0
12 2
13 1
14 2
15 0

Output:
200
100
149
100
149
52
97
52
360
97
5
2
2
2
5
1
1
2
4
5
5
2
2
2
5

Warning: enormous input/output data, be careful with certain languages


Added by:Fudan University Problem Setters
Date:2008-07-08
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Central European Programming Contest, Wrocław 2008

hide comments
2015-03-11 09:13:13 VISHAL DEEPAK AWATHARE
can anyone tell what is the range of x and Y ??
2012-09-30 23:36:41 karan173
again no java solutions!
2012-05-21 23:24:59 InCore
what do you mean by nearest neighbour???
Ah, now I understand... looks hard

Last edit: 2012-05-21 23:27:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.