2741. In case of failure

单点时限: 10.0 sec

内存限制: 256 MB

To help their clients deal with faulty Cash Machines, the board of The Planar Bank has decided to stick a label expressing sincere regret and sorrow of the bank about the failure on every ATM. The very same label would gently ask the customer to calmly head to the nearest Machine (that should hopefully work fine).

In order to do so, a list of two-dimensional locations of all n ATMs has been prepared, and your task is to find for each of them the one closest with respect to the Euclidean distance.

输入格式

The input contains several test cases. The very _rst line contains the number of cases t (t <=15) that follow. Each test cases begin with the number of Cash Machines n (2 <= n <= 105). Each of the next n lines contain the coordinates of one Cash Machine x; y (0 <= x; y <= 109) separated by a space. No two points in one test case will coincide.

输出格式

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

样例

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

1 人解决,4 人已尝试。

1 份提交通过,共有 14 份提交。

9.9 EMB 奖励。

创建: 11 年,11 月前.

修改: 4 年前.

最后提交: 1 年,3 月前.

来源: Central European Programming Contest 2008

题目标签