Tribes

Professor Bajtowicz is a historian. He recently proposed a bold hypothesis that explains how the first states appeared on the continent of Bajtopia. Right after the great migration, $n$ tribes lived there, and the territory of each tribe is a rectangle on the map whose sides are parallel to the sides of the map. Territories were allowed to overlap, so several cultures met in some regions.

The hypothesis says this. Once the intersection of two territories has positive area, the two tribes merge after a while. The new tribe then spreads over the smallest rectangle that contains both former territories. The sides of that rectangle are parallel to the sides of the map as well. The process continues until every pair of territories intersects in zero area, and the territories that remain at that moment are the first states.

The set of territories at the end is the same whatever order the merges happen in.

The professor handed you the map of the original tribes and asked you to replay the process his hypothesis describes. Report the territories of the states.

The first line contains one integer $n$ ($1 \le n \le 100\,000$), the number of original tribes in Bajtopia.

Each of the next $n$ lines contains four integers $x_1$, $x_2$, $y_1$, $y_2$ ($0 \le x_1 < x_2 \le 1\,000\,000$, $0 \le y_1 < y_2 \le 1\,000\,000$), meaning that one tribe held the territory drawn on the map as the rectangle with opposite corners $(x_1, y_1)$ and $(x_2, y_2)$.

Print one integer $m$ on the first line, the number of states that appear under the hypothesis.

Print $m$ more lines. Each of them contains four integers $x_1$, $x_2$, $y_1$, $y_2$ separated by single spaces, meaning that the territory of one state is the rectangle with opposite corners $(x_1, y_1)$ and $(x_2, y_2)$, where $x_1 < x_2$ and $y_1 < y_2$.

The quadruples are all different. Print them in lexicographic order: compare $x_1$ first, then $x_2$, then $y_1$, then $y_2$.