Professor Bajtowicz is a highly esteemed historian. He has recently developed a bold hypothesis explaining the process of the formation of the first states on the continent of Bajtopia. It is widely known that immediately after the great migration of peoples, these lands were inhabited by $n$ tribes. Interestingly, each of the tribes occupied a certain territory, which on the map of Bajtopia is a rectangle with sides parallel to the sides of the map. The territories did not have to be disjoint, so in some areas, several cultures met.

According to Professor Bajtowicz's hypothesis, if the intersection of the territories of two tribes had a positive area, then after some time these tribes would merge. This provided an impetus for further expansion, and the newly formed tribe would spread within the smallest rectangle (with sides parallel to the sides of the map) containing both of their previous territories.

Professor Bajtowicz claims that this process occurred continuously until, at some point, the intersection of every pair of territories had a zero area. At that point, the situation stabilized, and the areas occupied by the tribes transformed into the first states.

The professor knows that even his authority might not be enough for such an innovative hypothesis to be accepted by the ossified scientific community. Fortunately, thanks to his previous research, he has two accurate maps. One of them describes the locations of the original tribes, and the other describes the first states. Bajtowicz has secretly hired you to perform a simulation of the development of the tribes according to his model (based on the first map). When you provide him with the theoretical results, he will compare them with the actual distribution of states on the second map and determine whether his hypothesis has a chance of being true.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 100\,000$), representing the number of original tribes inhabiting Bajtopia. The next $n$ lines each contain four integers $x_1, x_2, y_1$, and $y_2$ ($0 \le x_1 < x_2 \le 1\,000\,000$, $0 \le y_1 < y_2 \le 1\,000\,000$), indicating that a certain tribe inhabited a territory which on the map is a rectangle whose two opposite vertices are $(x_1, y_1)$ and $(x_2, y_2)$.

Output

Your program should output in the first line a single integer $m$, representing the number of states that should be formed according to Bajtowicz's hypothesis. Then, your program should output $m$ lines, each containing four integers $x_1, x_2, y_1$, and $y_2$ separated by single spaces, indicating that the territory of one of the states is a rectangle on the map with opposite vertices $(x_1, y_1)$ and $(x_2, y_2)$, where $x_1 < x_2$ and $y_1 < y_2$. These quadruplets must be distinct and should be printed in lexicographical order.

Examples

Input 1

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

Output 1

2
1 6 2 9
7 8 1 4