시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 20 7 4 44.444%

문제

2차원 평면 상에 N개의 점이 주어진다. 

1 ≤ i, j ≤ N에 대해서 dist(i, j) = (xj - xi)2 + (yj - yi)2 라 정의할 때, 각각의 점 i에 대해서, Min(dist(i, j)) (1 ≤ j ≤ N, j ≠ i) 를 출력하라.

입력

입력은 여러 개의 테스트 케이스로 주어진다.

첫번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 15)가 주어진다.

이후 각각의 테스트 케이스마다, 첫번째 줄에 N (2 ≤ N ≤ 105) 이 주어진다. 이후 N개의 줄에 x, y가 주어진다 (0 ≤ x, y ≤ 109)

출력

각각의 테스트 케이스마다 N줄을 출력하라.

i번째 줄은 Min(dist(i, j)) (1 ≤ j ≤ N, j ≠ i)의 값이어야 한다.

예제 입력 1

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

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6Ijc4OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWFlNGNcdWM2YjQgXHVjODEwIFx1Y2MzZVx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+Mlx1Y2MyOFx1YzZkMCBcdWQzYzlcdWJhNzQgXHVjMGMxXHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjODEwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+MSAmbGU7Jm5ic3A7aSwgaiAmbGU7Jm5ic3A7Tlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgZGlzdChpLCBqKSA9ICh4PHN1Yj5qPFwvc3ViPiZuYnNwOy0geDxzdWI+aTxcL3N1Yj4pPHN1cD4yPFwvc3VwPiZuYnNwOysgKHk8c3ViPmo8XC9zdWI+Jm5ic3A7LSB5PHN1Yj5pPFwvc3ViPik8c3VwPjI8XC9zdXA+Jm5ic3A7XHViNzdjIFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWI1NGMsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTAgaVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIE1pbihkaXN0KGksIGopKSAoMSAmbGU7Jm5ic3A7aiAmbGU7IE4sIGogJm5lOyZuYnNwO2kpJm5ic3A7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFQgKDEgJmxlOyZuYnNwO1QgJmxlOyZuYnNwOzE1KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOICgyICZsZTsmbmJzcDtOICZsZTsgMTA8c3VwPjU8XC9zdXA+KSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgeCwgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKDAgJmxlOyB4LCB5ICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IE5cdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5pXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCZuYnNwO01pbihkaXN0KGksIGopKSAoMSAmbGU7Jm5ic3A7aiAmbGU7IE4sIGogJm5lOyZuYnNwO2kpXHVjNzU4IFx1YWMxMlx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzg5MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkluIGNhc2Ugb2YgZmFpbHVyZSIsImRlc2NyaXB0aW9uIjoiPHA+VG8gaGVscCB0aGVpciBjbGllbnRzIGRlYWwgd2l0aCBmYXVsdHkgQ2FzaCBNYWNoaW5lcywgdGhlIGJvYXJkIG9mIFRoZSBQbGFuYXIgQmFuayBoYXMgZGVjaWRlZCB0byBzdGljayBhIGxhYmVsIGV4cHJlc3Npbmcgc2luY2VyZSByZWdyZXQgYW5kIHNvcnJvdyBvZiB0aGUgYmFuayBhYm91dCB0aGUgZmFpbHVyZSBvbiBldmVyeSBBVE0uIFRoZSB2ZXJ5IHNhbWUgbGFiZWwgd291bGQgZ2VudGx5IGFzayB0aGUgY3VzdG9tZXIgdG8gY2FsbWx5IGhlYWQgdG8gdGhlIG5lYXJlc3QgTWFjaGluZSAodGhhdCBzaG91bGQgaG9wZWZ1bGx5IHdvcmsgZmluZSkuPFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIGRvIHNvLCBhIGxpc3Qgb2YgdHdvLWRpbWVuc2lvbmFsIGxvY2F0aW9ucyBvZiBhbGwgbiBBVE1zIGhhcyBiZWVuIHByZXBhcmVkLCBhbmQgeW91ciB0YXNrIGlzIHRvIGZpbmQgZm9yIGVhY2ggb2YgdGhlbSB0aGUgb25lIGNsb3Nlc3Qgd2l0aCByZXNwZWN0IHRvIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBUaGUgdmVyeSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgY2FzZXMgdCAodCAmbGU7IDE1KSB0aGF0IGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2VzIGJlZ2luIHdpdGggdGhlIG51bWJlciBvZiBDYXNoIE1hY2hpbmVzIG4gKDIgJmxlOyBuICZsZTsgMTA8c3VwPjU8XC9zdXA+KS4gRWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIGNvbnRhaW4gdGhlIGNvb3JkaW5hdGVzIG9mIG9uZSBDYXNoIE1hY2hpbmUgeCwgeSAoMCAmbGU7IHgsIHkgJmxlOyAxMDxzdXA+OTxcL3N1cD4pIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBObyB0d28gcG9pbnRzIGluIG9uZSB0ZXN0IGNhc2Ugd2lsbCBjb2luY2lkZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IG4gbGluZXMuIGktdGggb2YgdGhlbSBzaG91bGQgY29udGFpbiB0aGUgc3F1YXJlZCBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBpLXRoIEFUTSBmcm9tIHRoZSBpbnB1dCBhbmQgaXRzIG5lYXJlc3QgbmVpZ2hib3VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==