题目描述

昨天，当地游乐场新开放了一个景点：镜子迷宫。迷宫中的所有墙面都覆盖着镜子，游客很容易在无数倒影中失去方向。

迷宫的平面形状可以用一个多边形描述，该多边形的每条边都平行于 $x$ 轴或 $y$ 轴。

开放首日，许多游客在迷宫中迷失，以至于工作人员不得不进入迷宫帮助他们离开。为了更好地了解游客最容易在哪些位置迷路，工作人员决定安装一套监控系统。

该系统使用一束位于脚部高度、不可见的激光穿过镜厅。通过观察激光在何时、何处被游客挡住，就可以追踪游客的移动情况。

激光从多边形边界上的某一点出发，与墙面成 $45^\circ$ 角。每当激光碰到镜面时，其运动方向都会转过 $90^\circ$。

工作人员计划在激光最开始的 $m$ 个反射点处分别安装传感器。请按顺序求出这些传感器应安装的位置。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 5\times 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

输出

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

输出

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