描述

Jeff叔叔拥有一家玻璃店，销售用于窗户和相框的玻璃板。众所周知，玻璃板只能在切割时从边缘到边缘沿直线进行切割。下图展示了如何将一块玻璃板切割成三块较小的玻璃板。

Jeff叔叔通常的操作流程如下：首先收集各种客户所需的小矩形玻璃板的订单，然后将每个小矩形的位置标记在一块大矩形玻璃板上，确保标记的矩形互不重叠。最后，他执行一系列水平和垂直切割（每次切割必须从当前玻璃板的边缘到边缘），从而为所有客户生产出所需的玻璃板。

由于最后的切割阶段（将大玻璃板切割成小块）极其乏味，Jeff叔叔请求你的帮助。他需要一个程序，该程序给定一块大矩形玻璃板以及每个标记矩形的左下角和右上角坐标，确定可以执行边缘到边缘切割的顺序。这个切割顺序列表将被输入机器，自动完成切割！

输入

输入包含多个测试用例。每个测试用例的第一行包含一个整数N，表示订单中的窗户和相框数量（2≤N≤2000）。接下来的N行每行包含四个整数X1, Y1, X2, Y2，其中(X1,Y1)和(X2,Y2)表示Jeff叔叔在大玻璃板上标记的矩形的左下角和右上角坐标（−5000≤X1,Y1,X2,Y2≤5000；且满足X1<X2和Y1<Y2）。每个测试用例需满足以下条件：

所有标记的矩形互不重叠（但可能在边界点相交），并且完全分割大玻璃板为若干矩形区域，即没有玻璃浪费。这意味着大玻璃板的左下角和右上角坐标可以通过标记矩形的坐标推断得出。 可以通过一系列边缘到边缘的切割将大玻璃板分割为所有标记的小矩形。 输入以N=0结束。

输出

对于每个测试用例，输出必须按特定顺序排列的切割操作列表。每行描述一个切割，用四个整数X1, Y1, X2, Y2表示切割的两个端点：

水平切割满足X1<X2且Y1=Y2。 垂直切割满足X1=X2且Y1<Y2。 切割顺序的优先级规则：

如果存在多个可选切割，优先选择X1较小的切割。 若仍有多个选项，优先选择Y1较小的切割。 每个测试用例的输出后需留一空行。

输入数据 1

3
0 0 20 30
20 0 40 20
20 20 40 30
6
1 2 2 4
2 3 3 5
1 4 2 5
2 2 3 3
3 2 4 3
3 3 4 5
0

输出数据 1

20 0 20 30
20 20 40 20

2 2 2 5
1 4 2 4
2 3 4 3
3 2 3 3
3 3 3 5

来源

南美地区 2004