Уничтожение дронов
После того, как Ральф сбежал из своей игры, его начали искать - за ним было послано n специально обученных дронов. Однако, Ральф не так прост и занял оборонительную позицию с турелью в руках.
Внимательно оценив ситуацию, Ральф понял, что если рассмотреть плоскость, где он находится в начале координат - точке (0, 0), то получится, что i-й из дронов находится в точке с координатами (x[i]
, y[i]
). Однако, пока Ральф разведывал ситуацию, дроны его заметили, а значит пора действовать. За одну секунду Ральф может поразить из турели любого дрона, а все уцелевшие дроны после этого могут передвинуться в любую из 8 соседних для них по горизонтали, вертикали или диагонали точек (при этом некоторые дроны могут оказаться в точках с одинаковыми координатами).
Задача дронов - добраться до Ральфа, то есть до точки (0, 0), а задача Ральфа - поразить всех дронов, пока они до него не добрались. Со своей стороны Ральф гарантирует вам, что ни разу не промахнется и каждым выстрелом будет поражать ровно одного дрона. Вас же он просит сказать ему, в каком порядке их поражать. Помогите ему — скажите, в каком порядке поражать дронов, чтобы они не добрались до точки (0, 0), или скажите, что сделать этого не получится, и Ральфу лучше спасаться бегством.
Giriş verilənləri
В первой строке содержится количество дронов n (1 ≤ n ≤ 10^5
). В i-й из следующих n строк содержатся два числа x[i]
и y[i]
- координаты i-го дрона (|x[i]
|, |y[i]
| ≤ 10^5
). Гарантируется, что в точке (0, 0) нет дронов.
Çıxış verilənləri
В одной строке выведите n чисел от 1 до n - номера дронов в порядке, в котором Ральфу в них нужно стрелять. Если же какой-то дрон в любом случае доберется до точки (0, 0), выведите -1. Если существует несколько решений, выведите любое из них.