eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

В случае сбоя

В случае сбоя

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Чтобы объяснить клиентам как поступать в случае сбоя работы банкоматов, совет банка решил приклеивать наклейку, выражая искреннее сожаление и печаль банка об аварии на каждом таком банкомате. На этой же наклейке клиенту предлагалось пройти к ближайшему рабочему банкомату (который, как мы надеемся, безотказно работает).

Для этого был подготовлен список расположения всех n банкоматов. Ваша задача состоит в нахождении для каждого банкомата ближайшего к нему, используя евклидово расстояние.

Входные данные

Первая строка содержит количество тестов t (t15). Каждый тест начинается с количества банкоматов n (2n10^5). Каждая из следующих n строк содержит координаты одного банкомата x и y (0x, y10^9). Никакие координаты банкоматов не совпадают.

Выходные данные

Для каждого теста вывести n строк. i-ая строка должна содержать квадрат расстояния от 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
Источник 2008 ACM Central Europe, November 28-30, Problem J