C - 重新排序卡片

得分：$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$。

---

4 5 2
3 2
2 5

2 1
1 2

让 * 表示一张没写任何字的卡片。卡片的初始排列如下：

``` ***** ****2 *1*** *****```

操作结束后，它们将按以下方式排列：

``` *2 1*```

这里，卡片 $1$ 在从上往下数的第 $2$ 行，从左到右数的第 $1$ 列，卡片 $2$ 在从上往下数的第 $1$ 行，从左到右数的第 $2$ 列。

---

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

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