题目描述

我们有一个排列成 $H$ 行 $W$ 列的矩阵，共有 $HW$ 张卡片。

对于每个 $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***
*****```

在操作结束后，卡片的排列变为：

```plain
*2
1*```

此时，编号为 $1$ 的卡片位于从上往下数第 $2$ 行和从左往右数第 $1$ 列，而编号为 $2$ 的卡片位于从上往下数第 $1$ 行和从左往右数第 $2$ 列。

### 示例输入 2

```plain
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