C - Reorder Cards 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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 をこの順に空白区切りで出力せよ。

入力例 1

4 5 2
3 2
2 5

出力例 1

2 1
1 2

何も書かれていないカードを * で表すことにします。最初、カードの配置は以下の通りです。

*****
****2
*1***
*****

操作終了後、カードの配置は以下の通りになります。

*2
1*

1 が書かれたカードは上から 2 行目、左から 1 列目にあり、2 が書かれたカードは上から 1 行目、左から 2 列目にあります。

入力例 2

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

Score : 300 points

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

  • If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
  • If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

  • 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
  • All pairs (A_i,B_i) are distinct.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W N
A_1 B_1
\vdots
A_N B_N

Output

Print N lines.

If, after the end of the process, the card with the number i is at the C_i-th row from the top and D_i-th column from the left, the i-th line should contain C_i and D_i in this order with a space between them.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10