题目描述

一片田野可以看成一个 $10^9\times10^9$ 的方格图，行从北向南编号为 $1$ 到 $10^9$，列从西向东编号为 $1$ 到 $10^9$。第 $r$ 行、第 $c$ 列的格子记为 $(r,c)$。

田野里有 $n$ 只兔子，编号为 $1$ 到 $n$。最初，第 $i$ 只兔子位于格子 $(r_i,c_i)$，任意两只兔子的位置不同。

兔子会用后腿震踏地面。接下来将依次发生 $m$ 次震踏，第 $j$ 次震踏由第 $t_j$ 只兔子发起。每次震踏时，发起震踏的兔子位置不变，其余兔子同时远离它。

具体地，设发起震踏的兔子 A 与另一只兔子 B 的行号之差的绝对值为 $d_r$，列号之差的绝对值为 $d_c$。兔子 B 的移动规则如下：

• 若 $d_r<d_c$，则沿列方向远离 A 移动两格，行号不变。
• 若 $d_r=d_c$，则沿行方向和列方向各远离 A 移动一格。
• 若 $d_r>d_c$，则沿行方向远离 A 移动两格，列号不变。

每次移动均根据本次震踏发生前的位置计算。可以证明，任意一次震踏后，兔子的位置仍然两两不同。保证整个过程中没有兔子离开方格图，且兔子不会因震踏以外的原因移动。

你需要求出所有震踏结束后，每只兔子的位置。

输入格式

输入的第一行包含两个正整数 $n,m$，分别表示兔子数量和震踏次数。

接下来 $n$ 行，其中第 $i$ 行包含两个正整数 $r_i,c_i$，表示第 $i$ 只兔子的初始位置。

输入的最后一行包含 $m$ 个正整数 $t_1,t_2,\ldots,t_m$，依次表示每次发起震踏的兔子编号。

输出格式

输出 $n$ 行，其中第 $i$ 行包含两个正整数，依次表示第 $i$ 只兔子的最终行号和列号。

输入输出样例

2 1
1 1
2 2
1

1 1
3 3

说明/提示

样例 1 解释

第 $1$ 只兔子位于 $(1,1)$，第 $2$ 只兔子位于 $(2,2)$。两只兔子的行号之差和列号之差的绝对值相等。第 $1$ 只兔子震踏后，第 $2$ 只兔子向东南方向移动到 $(3,3)$，第 $1$ 只兔子的位置不变。

该样例满足测试点 $1\sim12$ 的约束条件。

样例 2

见附件中的 thumper/thumper2.in 与 thumper/thumper2.ans。

样例 2 解释

本次震踏由位于 $(7,7)$ 的第 $1$ 只兔子发起，其余兔子分别按照题目描述中的规则移动。例如，位于 $(3,7)$ 的兔子移动到 $(1,7)$，位于 $(4,4)$ 的兔子移动到 $(3,3)$。

该样例满足测试点 $1\sim12$ 的约束条件。

样例 3

见附件中的 thumper/thumper3.in 与 thumper/thumper3.ans。

该样例满足测试点 $13\sim21$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1\le n,m\le5\times10^5$；
• 对于所有 $i$（$1\le i\le n$），均有 $1\le r_i,c_i\le10^9$，且所有初始位置两两不同；
• 对于所有 $j$（$1\le j\le m$），均有 $1\le t_j\le n$；
• 整个震踏过程中，没有兔子离开方格图。

特殊性质 A：对于所有 $i$（$1\le i\le n$），均有 $r_i=1$。

附件

下载附加样例（thumper.zip）