В случае сбоя
Чтобы объяснить клиентам как поступать в случае сбоя работы банкоматов, совет банка решил приклеивать наклейку, выражая искреннее сожаление и печаль банка об аварии на каждом таком банкомате. На этой же наклейке клиенту предлагалось пройти к ближайшему рабочему банкомату (который, как мы надеемся, безотказно работает).
Для этого был подготовлен список расположения всех n банкоматов. Ваша задача состоит в нахождении для каждого банкомата ближайшего к нему, используя евклидово расстояние.
Входные данные
Первая строка содержит количество тестов t (t ≤ 15). Каждый тест начинается с количества банкоматов n (2 ≤ n ≤ 10^5). Каждая из следующих n строк содержит координаты одного банкомата x и y (0 ≤ x, y ≤ 10^9). Никакие координаты банкоматов не совпадают.
Выходные данные
Для каждого теста вывести n строк. i-ая строка должна содержать квадрат расстояния от i-го банкомата до его ближайшего соседа.