#abc213c. [abc213_c]Reorder Cards
[abc213_c]Reorder Cards
問題文
行 列の格子状に 枚のカードが並べられています。
について、上から 行目、左から 列目にあるカードには数 が書かれており、それ以外の 枚のカードには何も書かれていません。
これらのカードに対し、以下の 種類の操作を可能な限り繰り返します。
- 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
- 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める
操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。
制約
- は相異なる
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
行出力せよ。
操作終了後に数 が書かれたカードが上から 行目、左から 列目に存在するとき、 行目には をこの順に空白区切りで出力せよ。
入力例 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