Bunnyland 拥有广阔的田野，Bunnyland 矮兔（一种原生的兔子）在其中自由漫步。 其中一块田野可以建模为一个 $10^9 \times 10^9$ 的网格。网格的行从北到南编号为 $1$ 到 $10^9$，列从西到东编号为 $1$ 到 $10^9$。我们将位于第 $r$ 行第 $c$ 列的单元格称为单元格 $(r, c)$。

在这块田野中，有 $n$ 只兔子，编号为 $1$ 到 $n$。第 $i$ 只兔子最初位于单元格 $(r[i], c[i])$。初始时没有两只兔子位于同一个单元格。

兔子在烦躁时会抬起后腿踢地，这种动作被称为“跺脚”（thumping）。这 $n$ 只兔子将执行 $m$ 次跺脚。在第 $j$ 秒开始时，兔子 $t[j]$ 会跺脚。当一只兔子跺脚时，所有其他兔子都会远离这只跺脚的兔子。

具体来说，当兔子 A 跺脚时，兔子 B 的移动方式如下： 如果 A 和 B 之间的行数差小于列数差，B 将向远离 A 的方向移动两列。 如果 A 和 B 之间的行数差等于列数差，B 将向远离 A 的方向移动一列和一行。 * 如果 A 和 B 之间的行数差大于列数差，B 将向远离 A 的方向移动两行。

可以证明，跺脚发生后，兔子的位置仍然互不相同。

Benson 兔子在调查完有毒细菌退休后回来寻找他的同伴，但所有的跺脚声导致兔子们四散奔逃。请帮助 Benson 确定所有跺脚结束后 $n$ 只兔子的最终位置！

保证在跺脚序列中，兔子永远不会离开网格。你也可以假设除了跺脚之外，兔子在任何其他情况下都不会移动。

输入格式

你的程序必须从标准输入读取数据。 第一行包含两个空格分隔的整数 $n$ 和 $m$。 接下来的 $n$ 行，每行包含两个空格分隔的整数。第 $i$ 行包含 $r[i]$ 和 $c[i]$。 最后一行包含 $m$ 个空格分隔的整数 $t[1], t[2], \dots, t[m]$。

输出格式

你的程序必须打印到标准输出。 输出应包含 $n$ 行。第 $i$ 行应包含两个空格分隔的整数，表示所有跺脚结束后兔子 $i$ 的行号和列号。

子任务

对于所有测试用例，输入满足以下限制： $1 \le n, m \le 500\,000$ $1 \le r[i], c[i] \le 10^9$，对于所有 $1 \le i \le n$ $1 \le t[j] \le n$，对于所有 $1 \le j \le m$ $(r_i, c_i) \neq (r_j, c_j)$，对于所有 $i \neq j$ * 保证兔子在跺脚序列中永远不会离开网格。

你的程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

2 1
1 1
2 2
1

样例输出 1

1 1
3 3

说明 1

兔子 1 位于单元格 $(1, 1)$，兔子 2 位于单元格 $(2, 2)$。 由于兔子 1 和兔子 2 之间的行数差等于列数差，当兔子 1 跺脚时，兔子 2 将向远离兔子 1 的东南方向移动一列和一行，落在单元格 $(3, 3)$。跺脚的兔子 1 的位置不变。

样例输入 2

13 1
7 7
3 7
4 4
4 10
5 6
6 4
6 8
8 7
8 10
9 3
9 5
9 9
10 6
1

样例输出 2

7 7
1 7
3 3
3 11
3 6
6 2
5 9
10 7
8 12
9 1
10 4
10 10
12 6

说明 2

题目中的图对应于此测试用例。蓝色箭头显示了当位于 $(7, 7)$ 的兔子 1 跺脚时，其他兔子如何移动。

样例输入 3

3 2
1 10
1 20
1 30
1 3

样例输出 3

1 8
1 20
1 32