配点 : $300$ 点

問題文

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

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

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

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

制約

• $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