[AdditionalFile5268.zip](file://AdditionalFile5268.zip?type=additional_file)

#5268. 「NOISG 2025 Final」Thumper

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2025 Final T2. Thumper

在兔子大陆上，有广阔的田野，兔子大陆矮兔（一种本地兔子物种）在此自由漫步。其中一块田野可建模为一个 $10^{9} \times 10^{9}$ 的网格。网格的行从北到南编号为 $1$ 到 $10^{9}$，列从西到东编号为 $1$ 到 $10^{9}$。位于行 $r$ 和列 $c$ 的格子称为格子 $(r, c)$。

这片田野中有 $n$ 只兔子，编号从 $1$ 到 $n$。第 $i$ 只兔子初始位于格子 $(r[i], c[i])$。保证任意两只兔子的初始位置均不相同。

兔子在恼怒时会抬起后腿并跺地，这一动作称为跺脚。这 $n$ 只兔子将执行 $m$ 次跺脚序列。在第 $j$ 秒开始时，兔子 $t[j]$ 会跺脚。当一只兔子跺脚时，其他所有兔子会远离跺脚的兔子。

具体而言，当兔子 A 跺脚时，兔子 B 将按以下规则移动：

• 若 A 和 B 之间的行数差小于列数差，B 将沿列方向远离 A 移动两个单位。
• 若 A 和 B 之间的行数差等于列数差，B 将沿行和列方向各远离 A 移动一个单位。
• 若 A 和 B 之间的行数差大于列数差，B 将沿行方向远离 A 移动两个单位。

可以证明，跺脚后所有兔子的位置仍然保持不同。

兔子本森在研究有毒细菌退休后，前来寻找他的同伴，但跺脚动作导致兔子们四散。请帮助本森确定所有 $n$ 只兔子在跺脚序列结束后最终所在的位置！

保证在跺脚序列中，兔子不会离开网格。你也可以假设兔子仅在跺脚时移动，不会在其他情况下移动。

输入格式

程序需从标准输入读取数据。

输入的第一行包含两个空格分隔的整数 $n$ 和 $m$。

接下来的 $n$ 行，每行包含两个空格分隔的整数，第 $i$ 行表示 $r[i]$ 和 $c[i]$。

最后一行包含 $m$ 个空格分隔的整数 $t[1], t[2], \ldots, t[m]$。

输出格式

程序需向标准输出输出结果。

输出包含 $n$ 行，第 $i$ 行包含两个空格分隔的整数，表示兔子 $i$ 在所有跺脚结束后所在的行和列。

样例 1

输入

2 1
1 1
2 2
1

输出

1 1
3 3

兔子 $1$ 位于格子 $(1,1)$，兔子 $2$ 位于格子 $(2,2)$。

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

这个样例满足子任务 $1,3,4,5$ 的限制。

样例 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

输出

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

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

这个样例满足子任务 $1,3,4,5$ 的限制。

样例 3

输入

3 2
1 10
1 20
1 30
1 3

输出

1 8
1 20
1 32

这个样例满足所有子任务的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n, m \leq 500000$
• $1 \leq r[i], c[i] \leq 10^{9}$，对于所有 $1 \leq i \leq n$
• $1 \leq t[j] \leq n$，对于所有 $1 \leq j \leq m$
• 对于所有 $i \neq j$，$(r[i], c[i]) \neq (r[j], c[j])$
• 保证兔子在跺脚序列中不会离开网格。

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
$1$	$18$	$n, m \leq 2000$
$2$	$21$	$r[i]=1$
$3$	$32$	$n \leq 2000$
$4$	$13$	$n \leq 100000$
$5$	$16$	无附加限制