AT_abc213_c [ABC213C] Reorder Cards

[problemUrl]: https://atcoder.jp/contests/abc213/tasks/abc213_c $ 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 $ をこの順に空白区切りで出力せよ。

### 制約 - $ 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 $ 列目にあります。