시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUICgxICZsZTsmbmJzcDtUICZsZTsmbmJzcDsxNSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIE4gKDIgJmxlOyZuYnNwO04gJmxlOyAxMDxzdXA+NTxcL3N1cD4pIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCB4LCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMCAmbGU7IHgsIHkgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgTlx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwJm5ic3A7TWluKGRpc3QoaSwgaikpICgxICZsZTsmbmJzcDtqICZsZTsgTiwgaiAmbmU7Jm5ic3A7aSlcdWM3NTggXHVhYzEyXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3ODkwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSW4gY2FzZSBvZiBmYWlsdXJlIiwiZGVzY3JpcHRpb24iOiI8cD5UbyBoZWxwIHRoZWlyIGNsaWVudHMgZGVhbCB3aXRoIGZhdWx0eSBDYXNoIE1hY2hpbmVzLCB0aGUgYm9hcmQgb2YgVGhlIFBsYW5hciBCYW5rIGhhcyBkZWNpZGVkIHRvIHN0aWNrIGEgbGFiZWwgZXhwcmVzc2luZyBzaW5jZXJlIHJlZ3JldCBhbmQgc29ycm93IG9mIHRoZSBiYW5rIGFib3V0IHRoZSBmYWlsdXJlIG9uIGV2ZXJ5IEFUTS4gVGhlIHZlcnkgc2FtZSBsYWJlbCB3b3VsZCBnZW50bHkgYXNrIHRoZSBjdXN0b21lciB0byBjYWxtbHkgaGVhZCB0byB0aGUgbmVhcmVzdCBNYWNoaW5lICh0aGF0IHNob3VsZCBob3BlZnVsbHkgd29yayBmaW5lKS48XC9wPlxyXG5cclxuPHA+SW4gb3JkZXIgdG8gZG8gc28sIGEgbGlzdCBvZiB0d28tZGltZW5zaW9uYWwgbG9jYXRpb25zIG9mIGFsbCBuIEFUTXMgaGFzIGJlZW4gcHJlcGFyZWQsIGFuZCB5b3VyIHRhc2sgaXMgdG8gZmluZCBmb3IgZWFjaCBvZiB0aGVtIHRoZSBvbmUgY2xvc2VzdCB3aXRoIHJlc3BlY3QgdG8gdGhlIEV1Y2xpZGVhbiBkaXN0YW5jZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIFRoZSB2ZXJ5IGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBjYXNlcyB0ICh0ICZsZTsgMTUpIHRoYXQgZm9sbG93LiBFYWNoIHRlc3QgY2FzZXMgYmVnaW4gd2l0aCB0aGUgbnVtYmVyIG9mIENhc2ggTWFjaGluZXMgbiAoMiAmbGU7IG4gJmxlOyAxMDxzdXA+NTxcL3N1cD4pLiBFYWNoIG9mIHRoZSBuZXh0IG4gbGluZXMgY29udGFpbiB0aGUgY29vcmRpbmF0ZXMgb2Ygb25lIENhc2ggTWFjaGluZSB4LCB5ICgwICZsZTsgeCwgeSAmbGU7IDEwPHN1cD45PFwvc3VwPikgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIE5vIHR3byBwb2ludHMgaW4gb25lIHRlc3QgY2FzZSB3aWxsIGNvaW5jaWRlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBvdXRwdXQgbiBsaW5lcy4gaS10aCBvZiB0aGVtIHNob3VsZCBjb250YWluIHRoZSBzcXVhcmVkIGRpc3RhbmNlIGJldHdlZW4gdGhlIGktdGggQVRNIGZyb20gdGhlIGlucHV0IGFuZCBpdHMgbmVhcmVzdCBuZWlnaGJvdXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d