#abc213c. [abc213_c]Reorder Cards

[abc213_c]Reorder Cards

問題文

HHWW 列の格子状に HWHW 枚のカードが並べられています。
i=1,ldots,Ni=1,\\ldots,N について、上から AiA_i 行目、左から BiB_i 列目にあるカードには数 ii が書かれており、それ以外の HWNHW-N 枚のカードには何も書かれていません。

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

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

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

制約

  • 1leqH,Wleq1091 \\leq H,W \\leq 10^9
  • 1leqNleqmin(105,HW)1 \\leq N \\leq \\min(10^5,HW)
  • 1leqAileqH1 \\leq A_i \\leq H
  • 1leqBileqW1 \\leq B_i \\leq W
  • (Ai,Bi)(A_i,B_i) は相異なる
  • 入力に含まれる値は全て整数である

入力

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

HH WW NN A1A_1 B1B_1 vdots\\vdots ANA_N BNB_N

出力

NN 行出力せよ。

操作終了後に数 ii が書かれたカードが上から CiC_i 行目、左から DiD_i 列目に存在するとき、ii 行目には Ci,DiC_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