帕夏是一名年轻的技术人员,然而,他已经有了一个宏伟的目标:组装一台电脑。他必须熟悉的第一项任务是组装电气方案。
Pasha 昨天组装的方案由几条电线组成。每条线都是一个线段,连接平面上的两个点,线段 $$$[1, 10^9]$$$ 内具有整数坐标。
方案中有两种颜色的电线:
- 红线:这些线是水平线段,即如果这样的线连接两个点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$,则 $$$y_1 = y_2$$$;
- 蓝色导线:这些导线是垂直线段,即,如果这样的导线连接两个点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$,则 $$$x_1 = x_2$$$。
请注意,如果一条电线将一个点连接到其自身,则它可能是蓝色的,也可能是红色的。此外,在帕夏的方案中,没有两条相同颜色的线相交,即没有两条相同颜色的线有公共点。
Pasha的方案的缺陷在于电线没有被隔离,所以在两条不同颜色的电线相交的地方,Pasha看到了火花。帕夏写下了他看到火花的所有点,并获得了一组 $$$n$$$ 不同的点。之后他拆解了这个计划。
第二天早上,Pasha 看着他看到火花的那组 $$$n$$$ 点,想知道他使用了多少根电线。不幸的是,他不记得了,所以他现在想知道他在该方案中可能使用的最少电线数量是多少。帮助他确定这个数字,并以这样的方式放置电线,使得在最终的方案中火花出现在相同的位置。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) — Pasha 看到火花的点数。
接下来的 $$$n$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x, y \leq 10^9$$$) — 有火花的点的坐标。保证所有点都是不同的。
输出
按以下格式打印方案的描述。
在第一行中打印 $$$h$$$ — 水平红线的数量 ($$$0 \leq h$$$)。在接下来的 $$$h$$$ 行中,打印 $$$4$$$ 整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$、$$$y_2$$$ — 与此红线连接的两个点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 的坐标。该段必须是水平的,即 $$$y_1 = y_2$$$ 必须成立。此外,约束 $$$1 \leq x_1, y_1, x_2, y_2 \leq 10^9$$$ 必须成立。
之后打印 $$$v$$$ — 垂直蓝线的数量 ($$$0 \leq v$$$)。在接下来的 $$$v$$$ 行中,打印 $$$4$$$ 整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$、$$$y_2$$$ — 与这条蓝线连接的两个点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 的坐标。该段必须是垂直的,即 $$$x_1 = x_2$$$ 必须按住。此外,约束 $$$1 \leq x_1, y_1, x_2, y_2 \leq 10^9$$$ 必须成立。
相同颜色的两个线段不应有公共点。出现火花的点集应与输入中给出的点集相同。
段数 $$$(h + v)$$$ 应尽可能少。很容易看出答案总是存在的。如果有多个可能的答案,请打印其中一个。
示例
输入 #1
4 2 2 2 4 4 2 4 4
输出 #1
2 5 2 1 2 1 4 5 4 2 2 1 2 5 4 5 4 1
输入 #2
4 2 1 3 2 2 3 1 2
输出 #2
4 2 1 2 1 3 2 3 2 1 2 1 2 2 3 2 3 3 1 2 1 2 3 2 3 2 2 3 2 1
注意
在第一个示例中,Pasha 可以组合以下方案:
在此方案中,每种颜色有 $$$2$$$ 电线:红色电线将 $$$(5, 2)$$$ 与 $$$(1, 2)$$$ 连接,$$$(1, 4)$$$ 与 $$$(5, 4)$$$ 连接,蓝色电线将 $$$(2, 1)$$$ 与 $$$(2, 5)$$$ 连接, $$$(4, 5)$$$ 与 $$$(4, 1)$$$。请注意,火花出现在输入中描述的点中,它们在图片上以黄色显示。例如,Pasha 将在点 $$$(2, 4)$$$ 处看到火花,因为第二条红线和第一条蓝线在那里相交。可以证明,我们不能用少于 $$$4$$$ 的电线来生成具有相同火花位置的方案。