分数: 300 点
问题陈述
我们有 HW 卡片排列成矩阵 H 行和 W 列。
对于每个 i=1, \ldots, N,卡位于 A_i从顶部开始的第行和 B_i左起第 列有一个数字
上面写着 i 。另一个 HW-N 卡片上没有写任何内容。
我们将尽可能地对这些卡重复以下两种操作。
- 如果有一排没有编号的卡片,请取出该排中的所有卡片,并通过向上移动剩余的卡片来填补空白。
- 如果有一列没有编号的卡片,则移除该列中的所有卡片,并将剩余的卡片向左移动来填补空白。
上述过程结束后,找到每张编号卡的位置。可以证明,这些位置是唯一确定的,与操作执行的顺序无关。
约束
- 1 \leq H,W \leq 10^9
- 1 \leq N \leq \min(10^5,HW)
- 1 \leq A_i \leq H
- 1 \leq B_i \leq W
- 所有对 (A_i,B_i) 是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W N A_1 B_1 \vdots A_N B_N
输出
打印 N 行。
如果在该过程结束后,带有该号码的卡 i 位于 C_i从顶部开始的第行和 D_i左起第 列, i- 第行应包含 C_i 和 D_i 按此顺序,中间有一个空格。
示例输入 1
4 5 2 3 2 2 5
示例输出 1
2 1 1 2
让 * 代表一张上面没有写任何东西的卡片。卡片的初始排列是:
***** ****2 *1*** *****
流程结束后,将进行如下安排:
*2 1*
这里,该卡带有 1 位于 2- 从顶部开始的第 1 行和 1- 从左边算起第 1 列,以及带有 2 位于 1- 从顶部开始的第 1 行 2- 左起第 2 列。
示例输入 2
1000000000 1000000000 10 1 1 10 10 100 100 1000 1000 10000 10000 100000 100000 1000000 1000000 10000000 10000000 100000000 100000000 1000000000 1000000000
示例输出 2
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10