分数: 425 点
问题陈述
有 N 一块放在桌子上的巧克力块。 件 i\ (1 \leq i \leq N) 是一个矩形 h_i 块高大且 w_i 块宽。
已知这些碎片是通过以下程序获得的。
- 首先拿着一块巧克力棒 H 块高大且 W 块宽。桌子上没有放置任何东西。
- 重复以下操作 N-1 次。
- 将当前手上的棋子分成两块。分割后的两块都必须是沿着块边界的矩形。
- 将其中一块放在桌子上,并将另一块放在手中。
- 最后,将手中的棋子放在桌子上。
找到一种方法来安排 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