AT_abc445_d [ABC445D] Reconstruct Chocolate

$ 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 $ ブロックのピースとして配置することはできない。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 条件を満たす並べ方が複数存在する場合、どれを出力しても正解とみなされる。

### Sample Explanation 1 出力例の並べ方を図示すると以下のようになります。  ### 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 $ - 入力は問題文中の手順で得られたことが保証される - 入力はすべて整数