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

你整理出了 $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$, $di{r}_i$。若 $di{r}_i=0$，则 $r_i$ 放置在 $(x_i,y_i)\sim (x_i+w_i,y_i+h_i)$ 的矩形范围内；若 $di{r}_i=1$，则 $r_i$ 放置在 $(x_i,y_i)\sim (x_i+h_i,y_i+w_i)$的矩形范围内。

请注意确保你的输出格式正确，且 $c_i,di{r}_i\in \{0,1\}$。对于 $type=1$ 的测试点，所有 $c_i$ 均应为 $1$。

同一行中输出的整数应以一个空格分隔开。

样例一

input

1 3
1 1
1 1
2 1

output

1 0 0 0
1 0 1 0
1 1 0 1

样例二

input

2 4
2 2
1 1
1 1
2 1
2 1

output

1 0 0 0
1 0 1 0
1 1 0 1
0

评分方法

评分准则 nowhere1.ans$\sim$nowhere10.ans 已放在试题目录下。

每个测试点设置了 $10$ 个评分参数 $a_1,a_2,\cdots ,a_{10}$。若选手输出不合法，则得零分。否则，对于安放方式 $1$，令 $val$ 为 $R$ 的面积，若 $val\le a_i$，则你可获得 $i$ 分；对于安放方式 $2$，令 $val$ 为安放到 $R$ 中的思绪个数，若 $val\ge a_i$ 则你可获得 $i$ 分。满足多个得分条件，测试点得分取最高者。

下载

样例数据下载