题目描述

题目译自 PA 2014 Runda 5 Plemiona

Bajtowicz 教授是一位备受尊敬的历史学家。最近，他提出了一个大胆的假设，解释了拜托皮亚大陆上首批国家的形成过程。众所周知，在大迁徙之后，这些土地上居住着 $n$ 个部落。有趣的是，每个部落占据的领土在拜托皮亚地图上是一个与地图边框平行的矩形。这些领土不一定是互斥的，因此在某些地区，多种文化会交汇。

根据 Bajtowicz 教授的假设，只要两个部落领土的交集面积为正，经过一段时间后，这两个部落就会合并。这会刺激进一步的扩张，新形成的部落会在包含两者原有领土的最小矩形（边框与地图边框平行）内扩散。

Bajtowicz 教授认为，这一过程会持续进行，直到任意两个领土的交集面积为零为止。此时，局势稳定下来，部落占据的区域演变为首批国家。

教授知道，即使凭借他的权威，这一创新假设也未必能被僵化的学术界接受。幸运的是，凭借之前的研究，他拥有两张精确的地图。一张地图描述了原始部落的位置，另一张地图则记录了首批国家的分布。Bajtowicz 秘密聘请你根据第一张地图，按照他的模型模拟部落的发展过程。当你提供理论结果后，他会将其与第二张地图上国家的实际分布进行比较，以判断他的假设是否有可能成立。

输入格式

输入数据的第一行包含一个整数 $n$ $(1 \leq n \leq 100000)$，表示居住在拜托皮亚的原始部落数量。

接下来的 $n$ 行每行包含四个整数 $x_{1}, x_{2}, y_{1}, y_{2}$ $(0 \leq x_{1} < x_{2} \leq 1000000, 0 \leq y_{1} < y_{2} \leq 1000000)$，表示某个部落占据的领土在地图上是一个矩形，其对角顶点为 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$。

输出格式

第一行输出一个整数 $m$，表示根据 Bajtowicz 教授的假设应形成的国家数量。

随后，程序应输出 $m$ 行，每行包含四个用单个空格分隔的整数 $x_{1}, x_{2}, y_{1}, y_{2}$，表示某个国家的领土在地图上是一个矩形，其对角顶点为 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$，且满足 $x_{1} < x_{2}$，$y_{1} < y_{2}$。这些四元组必须互不相同，并按字典序排列输出。

5
7 8 1 4
1 5 2 3
4 5 2 7
2 3 5 9
4 6 8 9

2
1 6 2 9
7 8 1 4