AT_abc445_d [ABC445D] Reconstruct Chocolate

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.

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 $

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 Explanation 1 The arrangement in the sample output is illustrated below.  ### 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.