[PA2014]Plemiona

时间限制:30s      空间限制:384MB

题目描述

远古时代,在吉丽王国的版图上分布着n个部落。建立平面直角坐标系后,每个部落都是一个边平行于坐标轴的矩形。有些地盘可能同时属于多个部落。随着时间推移,部落之间会发生融合。具体来说,若两个部落的公共面积严格大于零,它们会合并成一个新的部落,新部落的形状是包含原来两个部落的最小矩形(边平行于坐标轴)。
数百万年后,部落之间终于达到了稳定状态(任两个部落都不能再合并了),然而吉丽也已经老了。他想知道最终还剩下几个部落,以及各个部落的位置。你能替他完成遗业吗?


输入格式

第一行一个整数n(1<=n<=100000),表示远古时代的部落数量。
接下来n行,每行四个整数x1,x2,y1,y2(0<=x1<x2<=1000000,0<=y1<y2<=1000000),表示部落的坐标。


输出格式

第一行输出一个整数m,表示稳定后还剩下的部落数量。
接下来m行,每行四个整数x1,x2,y1,y2,表示部落的坐标。请按照字典序(先比较x1,若x1相等则比较x2,以此类推)从小到大输出。


样例输入

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

提示

没有写明提示


题目来源

鸣谢Jcvb