题目描述

$H$ 行 $W$ 列の格子状に $HW$ 枚のカードが並べられています。
$i=1,\ldots,N$ について、上から $A_i$ 行目、左から $B_i$ 列目にあるカードには数 $i$ が書かれており、それ以外の $HW-N$ 枚のカードには何も書かれていません。

これらのカードに対し、以下の $2$ 種類の操作を可能な限り繰り返します。

• 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
• 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める

操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $N$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$

输出格式

$N$ 行出力せよ。

操作終了後に数 $i$ が書かれたカードが上から $C_i$ 行目、左から $D_i$ 列目に存在するとき、$i$ 行目には $C_i,D_i$ をこの順に空白区切りで出力せよ。

题目大意

在 $H$ 行 $W$ 列的矩阵中分布着 $N$ 个关键点。现在将所有不包括关键点的行或列全部删除（删除后将相邻的行/列接在一起），求删除之后所有关键点在矩阵中的新位置。

输出时按照关键点的输入顺序输出关键点的新位置。

4 5 2
3 2
2 5

2 1
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\ \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)$ は相異なる
• 入力に含まれる値は全て整数である

Sample Explanation 1

何も書かれていないカードを \* で表すことにします。最初、カードの配置は以下の通りです。 \*\*\*\*\* \*\*\*\*2 \*1\*\*\* \*\*\*\*\* 操作終了後、カードの配置は以下の通りになります。 \*2 1\* $1$ が書かれたカードは上から $2$ 行目、左から $1$ 列目にあり、$2$ が書かれたカードは上から $1$ 行目、左から $2$ 列目にあります。