У разі збою#5739
Щоб інформувати клієнтів про дії у разі збою роботи банкоматів, рада банку вирішила розміщувати наліпки, які висловлюють щире співчуття та жаль банку з приводу аварії на кожному такому банкоматі. На цій же наліпці клієнтам пропонується перейти до найближчого робочого банкомата (який, як ми сподіваємося, працює безвідмовно).
Для цього був складений список розташування всіх банкоматів. Ваше завдання — знайти для кожного банкомата найближчий до нього, використовуючи евклідову відстань.
Перший рядок містить кількість тестів (t \le 15). Кожен тест починається з кількості банкоматів (2 \le n \le 10^5). Кожен з наступних рядків містить координати одного банкомата та (0 \le x, y \le 10^9). Жодні координати банкоматів не збігаються.
Для кожного тесту виведіть рядків. -ий рядок повинен містити квадрат відстані від -го банкомата до його найближчого сусіда.
Приклад 1