题目描述

希尔伯特曲线的构造方法是一个递归过程，要构造n阶的希尔伯特曲线，先构造4个n-1阶的希尔伯

特曲线，这4个n-1阶的希尔伯特曲线通过特定的顺序连接起来。

以图像中央为原点，划分象限

观察发现：第一象限图形为前一阶数图形绕中心逆时针旋转90度并做轴对称所得

第三、四象限图形为原图形

        第二象限图形为前一阶数图形绕中心顺时针旋转90度并做轴对称所得

        且每一象限之间通过单位长度的线段，将上一象限图形的终点与下一象限图形的起点连接

希尔伯特曲线的每一级迭代通常可以用以下步骤描述：

第0阶： 从一个点或者一个简单的线段开始，作为迭代的基础。

第1阶： 将现有的线段分为四份，然后按特定的顺序和方向通过这些点构建一个环形的路径。

更高阶： 对于每一阶迭代，都取前一阶曲线，按照规则复制四份，然后进行旋转和连接，形成新的一阶曲线。

前三阶希尔伯特曲线如下所示。

而希尔伯特排序则是希尔伯特曲线的重要应用，现在给你$N$个点，你需要根据曲线经过的先后顺序对他进行排序

输入描述

第一行包含两个整数 n、k $(1 \leq n \leq 10^6, 1 \leq k \leq 30)$，即要排序的单元格数量和希尔伯特曲线的阶数

接下来的 n 行，每行包含两个整数 $x_i，y_i$，分别表示第 $x_i$ 行和第$y_i$ 列的单元格。输入中的所有单元格都是不同的。

输出描述

用 n 行输出已排序单元格的坐标。

样例

样例输入#1

5 2
2 4
2 3
1 1
3 1
4 3

样例输出#1

1 1
3 1
4 3
2 4
2 3

样例输入#2

4 1
1 1
1 2
2 1
2 2

样例输出#2

1 1
2 1
2 2
1 2