卡片重排

题目描述

我们有 $HW$ 张卡片,排列成 $H$ 行 $W$ 列的矩阵。

对于每个 $i=1, \ldots, N$,从上数第 $A_i$ 行、从左数第 $B_i$ 列的卡片上写着数字 $i$。其余 $HW-N$ 张卡片上什么都没写。

只要可以进行以下两种操作,我们就不断重复进行:

• 如果存在没有任何数字卡片的一行,则删除该行的所有卡片,并将剩余的卡片整体向上移动填补空缺。
• 如果存在没有任何数字卡片的一列,则删除该列的所有卡片,并将剩余的卡片整体向左移动填补空缺。

请找出上述过程结束后每张有数字卡片的位置。可以证明,这些位置唯一确定,与操作的执行顺序无关。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $1 \le H, W \le 10^9$
• $1 \le N \le \min(10^5, HW)$
• $1 \le A_i \le H$
• $1 \le B_i \le W$
• 所有 $(A_i, B_i)$ 各不相同
• 输入均为整数