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