Safe Shortest Paths

In a city, an infinite grid of two-way streets creates numerous intersections. The intersections of horizontal and vertical streets are called crossroads. Initially, there are some crossroads equipped with traffic lights. A road between two adjacent intersections is considered safe if both endpoints have a traffic light; otherwise, making turns on that road is dangerous.

For any two initial traffic lights, there must be at least one Manhattan shortest path between them in which every intersection along that path is equipped with a traffic light. You are allowed to install extra traffic lights on intersections to achieve this safety condition. One valid strategy is to install traffic lights on every intersection within the axis-aligned bounding box of the initial traffic lights.

Formally, suppose you are given N initial traffic lights located at distinct coordinates. Let [ x_{min} = \min{ x_i }, \quad x_{max} = \max{ x_i }, \quad y_{min} = \min{ y_i }, \quad y_{max} = \max{ y_i }, ] then a valid solution is to equip with traffic lights every intersection (x, y) where [ x_{min} \le x \le x_{max} \quad \text{and} \quad y_{min} \le y \le y_{max}. ] The extra traffic lights you install are those intersections in the bounding box that are not initially equipped.

Your task is to output the extra traffic lights you add such that the final configuration (initial plus extra) satisfies the safety condition.

Note: You may assume that the area of the bounding box (((x_{max}-x_{min}+1)\times(y_{max}-y_{min}+1))) is reasonably small so that iterating over all intersections in the rectangle is computationally feasible.

inputFormat

The first line contains an integer N (N (\ge) 2), the number of initial traffic lights.

The next N lines each contain two integers x and y, representing the coordinates of an initial traffic light. It is guaranteed that all coordinates are distinct and that 0 (\le) x, y (\le) 10^9.

outputFormat

First, output an integer K — the number of extra traffic lights added.

Then output K lines, each line containing two integers x and y, representing the coordinates of an extra traffic light. The extra traffic lights should be output in lexicographical order (sorted first by x, then by y).

sample

3
1 1
1 3
3 3

6
1 2
2 1
2 2
2 3
3 1
3 2