昨天，当地游乐场开放了一个新景点：镜子迷宫。这是一个所有墙壁都覆盖着镜子的迷宫，游客在反射的海洋中会失去方向感。迷宫的布局可以用一个所有边都平行于 $x$ 轴或 $y$ 轴的多边形来描述。

在开业当天，许多游客迷路了，以至于游乐场工作人员不得不介入并帮助他们找到出口。为了更好地了解游客在何处最容易迷路，工作人员决定安装一套监控系统。该系统包含一条在脚踝高度穿过镜子迷宫的隐形激光束，以便通过观察激光束在何时何地被中断来追踪游客的移动。

激光束从多边形的某个边界点出发，与墙壁成 45 度角。每当它撞击到镜子时，它会以 90 度角反射。为了使监控系统正常工作，工作人员计划在激光束的前 $m$ 个反射点处安装传感器。请找出需要安装传感器的位置。

图 M.1：第二个样例的示意图。

输入格式

输入包含： 一行，包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 5 \cdot 10^5$)，分别表示多边形的顶点数和反射次数。 $n$ 行，每行包含两个整数 $x$ 和 $y$，表示一个顶点的坐标。 * 一行，包含整数 $x_s$ 和 $y_s$，表示起点的坐标。

此外，输入满足以下约束条件： 多边形的顶点按逆时针顺序给出。 多边形的边互不接触或相交，除了相邻的边共享端点外。 多边形的边交替为水平和垂直。 多边形的周长（所有边的总长度）不超过 $10^6$。 输入中所有坐标的绝对值均不超过 $10^6$。 多边形所有顶点的坐标均为偶数，且起点的坐标中恰有一个为偶数（因此激光永远不会击中多边形的顶点）。 起点位于多边形的边界上。 激光束的初始方向为 $(1, 1)$，且该方向指向多边形内部。

输出格式

输出 $m$ 行，每行包含两个整数 $x$ 和 $y$，按顺序给出反射点的位置坐标。

样例

样例输入 1

4 6
0 0
10 0
10 10
0 10
1 0

样例输出 1

10 9
9 10
0 1
1 0
10 9
9 10

样例输入 2

10 10
-2 -2
8 -2
8 8
4 8
4 0
2 0
2 6
-4 6
-4 2
-2 2
4 1

样例输出 2

8 5
5 8
4 7
8 3
3 -2
-4 5
-3 6
2 1
-1 -2
-2 -1