Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
На плоскости расположены n точек (xi, yi) с целочисленными координатами от 0 до 106. Расстоянием между двумя точках с номерами a и b назовем следующую величину: (расстояние, вычисляемое по такой формуле, называется манхеттенским расстоянием).
Назовем гамильтоновым путем некоторую перестановку pi от 1 до n. Назовем длиной этого пути величину .
Найдите какой-нибудь гамильтонов путь с длиной не более, чем 25 × 108. Обратите внимание, минимизировать длину гамильтонова пути не требуется.
Входные данные
В первой строке дано число n (1 ≤ n ≤ 106).
В i + 1-й строке даны координаты точки с номером i: xi и yi (0 ≤ xi, yi ≤ 106).
Гарантируется, что никакие две точки не совпадают.
Выходные данные
Выведите перестановку чисел pi от 1 до n — искомый гамильтонов путь. Перестановка должна удовлетворять неравенству .
Если возможных ответов несколько, разрешается вывести любой.
Гарантируется, что существует подходящая перестановка.