Hilbert Sort

In a database, keeping items in the order of a numeric key makes one item easier to find and uses the CPU cache better: a contiguous block of memory then holds items with similar keys. That helps when you want to read every item whose key falls in a given range.

The situation gets harder when the keys are points on a 2D grid, as in a GPS guidance system. If the points $(x, y)$ are sorted by $x$ first and by $y$ only to break ties, two points that sit next to each other in memory have similar $x$ but can have very different $y$, so they can lie far apart on the grid. To preserve distances better, sort the data along a continuous space-filling curve.

The space-filling curve used here is the Hilbert curve. It starts at the origin $(0, 0)$, ends at $(S, 0)$, and on the way it passes through the whole axis-aligned square whose corners are $(0, 0)$ and $(S, S)$. Its construction is recursive: split the square into four quadrants that meet at $(S/2, S/2)$, and fill each quadrant with a suitably rotated and scaled copy of the entire Hilbert curve. First, the lower left quadrant is filled with a curve going from $(0, 0)$ to $(0, S/2)$. Second, the upper left quadrant is filled from $(0, S/2)$ to $(S/2, S/2)$. Third, the upper right quadrant is filled from $(S/2, S/2)$ to $(S, S/2)$. Finally, the lower right quadrant is filled from $(S, S/2)$ to $(S, 0)$. The Hilbert curve can also be defined as the limit of a sequence of curves. The figure shows the first six curves of that sequence.

You are given the positions of some locations of interest. Sort them by the order in which the Hilbert curve visits them. The curve meets itself at infinitely many places, for example at $(S/2, S/2)$, but $S$ is odd, so every integer point is visited exactly once.

The first line contains two integers $n$ and $S$ separated by a space ($1 \le n \le 200\,000$, $1 \le S < 10^9$, $S$ is odd). Each of the next $n$ lines describes one location of interest. Line $i + 1$ contains the integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le S$) and an identifier string, separated by spaces. The identifier is at most 46 characters long and uses only uppercase letters, lowercase letters, and digits. No two locations share a position, and no two locations share an identifier.

Print the $n$ identifiers, one per line, in the order in which the Hilbert curve visits the locations.