说明

你整理出了 $n$ 条思绪，它们在你的心中是一个个矩形 $r_i$，你想要在心中用一个大矩形 $R$ 安放它们，也就是将 $r_i$ 放置在 $R$ 内部。为了保护这些思绪，它们安放的位置不能与其他思绪有重合部分，并且四条边要平行或垂直于 $R$ 的边。两个思绪有重合部分，指它们安放位置的重合面积大于零。

你有两种安放方式：

1. 将 $n$ 条思绪全部安放进R 中，希望令 $R$ 的面积尽量小。
2. 固定 $R$ 的大小，希望将尽量多的思绪安放进 $R$ 中。

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

输入格式

第一行两个整数 $type, n$，分别表示安放方式与思绪的个数。

若 $type = 2$，第二行两个整数 $W, H$，表示 $R$ 的边长。

接下来 $n$ 行每行两个整数 $w_i, h_i$，表示第 $i$ 个思绪即 $r_i$ 的边长。

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

输出格式

为了方便，若 $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$, $d_{ir_i}$。若 $d_{ir_i} = 0$，则 $r_i$ 放置在 $(x_i, y_i)\sim(x_i + w_i, y_i + h_i)$ 的矩形范围内；若 $d_{ir_i} = 1$，则 $r_i$ 放置在 $(x_i, y_i)\sim(x_i + h_i, y_i + w_i)$ 的矩形范围内。

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

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

1 3
1 1
1 1
2 1

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

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

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

提示

评分方式

每个测试点设置了 $10$ 个评分参数 $a_1, a_2, ..., a_{10}$。若选手输出不合法，则得零分。

否则，对于安放方式 $1$，令 $val$ 为 $R$ 的面积，若 $val \leq a_i$，则你可获得 $i$ 分；对于安放方式 $2$，令 $val$ 为安放到 $R$ 中的思绪个数，若 $val \geq a_i$ 则你可获得 $i$ 分。满足多个得分条件，测试点得分取最高者。