AT_abc445_d [ABC445D] Reconstruct Chocolate

桌子上放着 $N$ 块巧克力，每块编号为 $i\ (1 \leq i \leq N)$，第 $i$ 块为高 $h_i$、宽 $w_i$ 的矩形。 已知这些巧克力块是通过如下操作获得的： - 开始时，手上有一块高 $H$、宽 $W$ 的完整巧克力，桌子上还没有放置任何巧克力块。 - 反复进行如下操作 $N-1$ 次： - 将手上的一块巧克力在块的边界处分成两个部分，分割后得到的两块依然是矩形。 - 把其中一块放在桌子上，手上保留另一块。 - 最后一步，将手上剩下的那块巧克力也放在桌子上。 请你找出一种方式，将这 $N$ 块巧克力拼成高 $H$、宽 $W$ 的矩形，满足以下条件： - 不同的块之间不能重叠。 - 不允许旋转巧克力，即对于 $h \neq w$，高 $h$、宽 $w$ 的巧克力不能以高 $w$、宽 $h$ 的形式放置。

输入通过标准输入给出，格式如下： > $H\ W\ N\ h_1\ w_1\ h_2\ w_2\ \ldots\ h_N\ w_N$

对于每一块巧克力 $i\ (1 \leq i \leq N)$，设其左上角放置在整个大矩形的第 $x_i$ 行、第 $y_i$ 列（从左上角起，分别从上到下、从左到右计数）。请输出如下格式： > $x_1\ y_1\ x_2\ y_2\ \ldots\ x_N\ y_N$ 如果存在多种合法的方案，输出任意一种即可。

### 样例解释 1 样例输出展示的拼法如下图所示：  ### 数据范围 - $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$ - 保证输入数据是按照题目描述中的方式分割得到的。 - 所有输入均为整数。 由 ChatGPT 5 翻译