D - Reconstruct Chocolate 解説 /

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

配点 : 425 点

問題文

N 個の板チョコのピースが机の上に置かれています。 i\ (1 \leq i \leq N) 番目のピースは縦 h_i ブロック、横 w_i ブロックの長方形状です。

これらのピースは以下の方法で得られたことがわかっています。

  • はじめに縦 H ブロック、横 W ブロックの板チョコを手に持つ。机には何も置かれていない。
  • 以下の操作を N-1 回繰り返す。
    • 現在手に持っているピースを 2 つに分割する。分割した後のピースはどちらもブロックの境界に沿った長方形でなくてはならない。
    • 一方のピースを机に置き、もう一方のピースは手に持ったままにする。
  • 最後に手に持っているピースを机に置く。

以下の条件を満たすように N 個のピースを縦 H ブロック、横 W ブロックの長方形状に並べる方法を一つ求めてください。

  • 異なるピース同士は重ならない。
  • ピースは回転してはいけない。すなわち h\neq w に対して縦 h ブロック、横 w ブロックのピースを縦 w ブロック、横 h ブロックのピースとして配置することはできない。

制約

  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 2 \leq N \leq 2\times 10^5
  • 1 \leq h_i \leq H
  • 1 \leq w_i \leq W
  • 入力は問題文中の手順で得られたことが保証される
  • 入力はすべて整数

入力

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

H W N
h_1 w_1
h_2 w_2
\vdots
h_N w_N

出力

条件を満たす並べ方において i\ (1 \leq i \leq N) 番目のピースの一番左上のブロックが全体で上から x_i 行目、左から y_i 列目のブロックに位置するとき、以下の形式で出力せよ。

x_1 y_1
x_2 y_2
\vdots
x_N y_N

条件を満たす並べ方が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

4 6 6
2 2
1 4
3 1
1 2
3 1
4 2

出力例 1

2 2
4 1
1 1
1 2
1 4
1 5

出力例の並べ方を図示すると以下のようになります。

入力例 2

100 100 20
72 7
4 74
17 67
20 67
96 3
1 95
5 81
87 3
3 87
16 67
95 8
100 2
92 1
3 98
92 5
87 3
1 98
19 67
11 74
87 1

出力例 2

7 89
90 22
62 22
7 22
4 96
99 1
94 15
7 19
4 9
27 22
4 1
1 99
7 14
1 1
7 9
7 16
100 1
43 22
79 22
7 15

Score : 425 points

Problem Statement

There are N pieces of a chocolate bar placed on a table. Piece i\ (1 \leq i \leq N) is a rectangle of h_i blocks tall and w_i blocks wide.

It is known that these pieces were obtained by the following procedure.

  • Start by holding a chocolate bar of H blocks tall and W blocks wide. Nothing is placed on the table.
  • Repeat the following operation N-1 times.
    • Split the piece currently in hand into two pieces. Both pieces after splitting must be rectangles along the block boundaries.
    • Place one of the pieces on the table, and keep the other piece in hand.
  • Finally, place the piece in hand on the table.

Find one way to arrange the N pieces into a rectangle of H blocks tall and W blocks wide satisfying the following conditions.

  • Different pieces do not overlap.
  • Pieces must not be rotated. That is, for h \neq w, a piece of h blocks tall and w blocks wide cannot be placed as a piece of w blocks tall and h blocks wide.

Constraints

  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 2 \leq N \leq 2\times 10^5
  • 1 \leq h_i \leq H
  • 1 \leq w_i \leq W
  • It is guaranteed that the input was obtained by the procedure described in the problem statement.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

H W N
h_1 w_1
h_2 w_2
\vdots
h_N w_N

Output

In a valid arrangement, let the top-left block of piece i\ (1 \leq i \leq N) be located at the x_i-th row from the top and the y_i-th column from the left of the whole rectangle. Output in the following format:

x_1 y_1
x_2 y_2
\vdots
x_N y_N

If there are multiple valid arrangements, any of them will be accepted.

Sample Input 1

4 6 6
2 2
1 4
3 1
1 2
3 1
4 2

Sample Output 1

2 2
4 1
1 1
1 2
1 4
1 5

The arrangement in the sample output is illustrated below.

Sample Input 2

100 100 20
72 7
4 74
17 67
20 67
96 3
1 95
5 81
87 3
3 87
16 67
95 8
100 2
92 1
3 98
92 5
87 3
1 98
19 67
11 74
87 1

Sample Output 2

7 89
90 22
62 22
7 22
4 96
99 1
94 15
7 19
4 9
27 22
4 1
1 99
7 14
1 1
7 9
7 16
100 1
43 22
79 22
7 15