A5866 | 「CTS2019 | CTSC2019」无处安放

**这是一道提交答案题。**

> 寂寥深夜，朦朦胧胧的月光为一切都笼上一层轻纱，你漫步在幽径，时而低头沉吟，时而凝望星空，只独孤与彷徨作伴，哪怕只言片语却也无人倾诉，万千思绪伴着你炽热的心，随风而动，无处安放……

你整理出了 $n$ 条思绪，它们在你的心中是一个个矩形 $r_i$，你想要在心中用一个大矩形 $R$ 安放它们，也就是将 $r_i$ 放置在 $R$ 内部。为了保护这些思绪，它们安放的位置不能与其他思绪有重合部分，并且四条边要平行或垂直于 $R$ 的边。两个思绪有重合部分，指它们安放位置的重合面积大于零。
你有两种安放方式：
1. 将 $n$ 条思绪全部安放进 $R$ 中，希望令 $R$ 的面积尽量小。
2. 固定 $R$ 的大小，希望将尽量多的思绪安放进 $R$ 中。

现在我已知晓你整理好的思绪，为你选择了安放的方式，我想知道你心中最好的安放方案，请你告诉我。

输入文件 nowhere1.in$\sim$nowhere10.in 已在试题目录下。
对于每组输入数据：
第一行两个整数 $type$, $n$，分别表示安放方式与思绪的个数。
若 $type = 2$，第二行两个整数 $W$, $H$，表示 $R$ 的边长。
接下来 $n$ 行每行两个整数 $w_i$, $h_i$，表示第 $i$ 个思绪即 $r_i$ 的边长。
同一行中输入的整数均以一个空格分隔开。

将输入文件对应的答案，输出到 nowhere1.out$\sim$nowhere10.out 中。
为了方便，若 $R$ 的边长为 $W$, $H$，我们将安放方案视作一个 $(0, 0) \sim (W, H)$ 的直角坐标系。注意对于 $type = 2$ 的测试点，你应按输入，将其视作 $(0, 0) \sim (W, H)$ 的坐标系，而不是 $(0, 0) \sim (H, W)$ 的坐标系。
输出共有 $n$ 行，每行一或四个整数，描述第 $i$ 个思绪即 $r_i$ 的放置方案。
每行第一个整数 $c_i$，其中 $c_i = 1$ 表示 $r_i$ 被安放在 $R$ 中；$c_i = 0$ 表示 $r_i$ 未被安放在 $R$ 中。
若 $c_i = 1$, 则该行接下来应输出三个整数 $x_i$, $y_i$, $dir_i$。若 $dir_i = 0$，则 $r_i$ 放置在 $(x_i, y_i) \sim (x_i +w_i, y_i +h_i)$ 的矩形范围内；若 $dir_i = 1$，则 $r_i$ 放置在 $(x_i, y_i) \sim (x_i +h_i, y_i +w_i)$的矩形范围内。
请注意确保你的输出格式正确，且 $c_i, dir_i \in \{0, 1\}$。对于 $type = 1$ 的测试点，所有 $c_i$ 均应为 $1$。
同一行中输出的整数应以一个空格分隔开。