Сортування Гільберта
Розміщення елементів у базах даних за числовим ключем не лише полегшує пошук певного елемента, але й дозволяє ефективніше використовувати кеш центрального процесора: будь-який сегмент даних, що є суміжним у пам'яті, описує елементи з подібними ключами. Це особливо корисно, коли потрібно отримати доступ до всіх елементів у певному діапазоні ключів. Однак ситуація ускладнюється, коли ключі є точками на 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 рядків - назви місць, кожну в окремому рядку, відсортовані у порядку відвідування їх кривою Гільберта.