Знищення дронів
Після втечі з гри, Ральфа почали шукати — за ним відправили n спеціально навчених дронів. Однак, Ральф не з простих і зайняв оборонну позицію з туреллю в руках.
Оцінивши ситуацію, Ральф зрозумів, що якщо розглянути площину, де він знаходиться в початку координат — точці (0, 0), то i-й дрон знаходиться в точці з координатами (x[i], y[i]). Але дрони його помітили, і тепер час діяти. За одну секунду Ральф може вразити з турелі будь-якого дрона, а всі уцілілі дрони після цього можуть пересунутися в будь-яку з 8 сусідніх для них по горизонталі, вертикалі або діагоналі точок (деякі дрони можуть опинитися в точках з однаковими координатами).
Завдання дронів — дістатися до Ральфа, тобто до точки (0, 0), а завдання Ральфа — вразити всіх дронів, поки вони до нього не дісталися. Ральф гарантує, що не промахнеться і кожним пострілом вразить рівно одного дрона. Він просить вас допомогти визначити, в якому порядку їх вражати. Допоможіть йому — скажіть, в якому порядку вражати дронів, щоб вони не дісталися до точки (0, 0), або скажіть, що це неможливо, і Ральфу краще рятуватися втечею.
Вхідні дані
У першому рядку міститься кількість дронів n (1 ≤ n ≤ 10^5). В i-му з наступних n рядків містяться два числа x[i] і y[i] — координати i-го дрона (|x[i]|, |y[i]| ≤ 10^5). Гарантується, що в точці (0, 0) немає дронів.
Вихідні дані
В одному рядку виведіть n чисел від 1 до n — номери дронів у порядку, в якому Ральфу потрібно в них стріляти. Якщо ж якийсь дрон у будь-якому випадку дістанеться до точки (0, 0), виведіть -1. Якщо існує декілька рішень, виведіть будь-яке з них.