Сортировка Гильберта
Размещение элементов в базах данных в соответствии с числовым ключом не только упрощает поиск определенного элемента, но также позволяет лучше использовать кэш Центрального Процессора: любой сегмент данных смежный в памяти, будет описывать элементы с похожими ключами. Это полезно, если, например, мы хотим получить доступ ко всем элементам, чьи ключи находятся в некотором диапазоне. Все становится сложнее, если ключи представляют собой точки на 2D-сетке, что имеет место в системе GPS-навигации. Если точки (x, y) сортируются сначала по x, а потом по y, то точки, смежные в памяти, будут иметь идентичные x координаты, но не обязательно одинаковые y координаты. Точки с одинаковыми y координатами могут располагаться далеко друг от друга на сетке. Для лучшего сохранения расстояния мы будем сортировать данные по непрерывной кривой, заполняющей пространство.
Рассмотрим одну такую кривую заполнения пространства, называемую кривой Гильберта. Кривая Гильберта начинается с начала координат (0, 0) и завершается в (S, 0), в процессе обхода посещая квадрат с углами (0, 0) и (S, S). Она имеет следующую рекурсивную конструкцию: разделим квадрат на четыре с общей точкой (S / 2, S / 2), и рекурсивно заполним каждый из них правильно повернутой и масштабированной копией полной кривой Гильберта. Сначала нижний левый квадрат заполняется кривой, идущей от (0, 0) до (0, S / 2). Затем верхний левый квадрат заполняется от (0, S / 2) до (S / 2, S / 2). Потом верхний правый квадрат заполняется от (S / 2, S / 2) до (S, S / 2). И наконец нижний правый квадрат заполняется от (S, S / 2) до (S, 0). С другой стороны гильбертова кривая может быть построена как математический предел последовательности кривых, первые шесть из которых показаны на рисунке.
Заданные местоположения Вас просят отсортировать в соответствии с посещением их кривой Гильберта. Заметим, что хотя кривая пересекает себя бесконечное число раз, например в точке (S / 2, S / 2), объявление S нечетным гарантирует нам, что все целые точки посещаются только один раз.
Входные данные
Первая строка содержит два целых числа n и S (1 ≤ n ≤ 200000, 1 ≤ S < 10^9, S нечетно). Далее следуют n строк. Строка i + 1 описывает i-ое место двумя целыми координатами x[i] и y[i] (0 ≤ x[i], y[i] ≤ S) и названием - строкой из не более чем 46 символов - букв и цифр (A - Z, a - z, 0 - 9). Никакие два места не имеют одинаковых координат или одинаковых названий.
Выходные данные
Выведите n строк - названий мест, каждое в отдельной строке, отсортированных в порядке посещения их кривой Гильберта.