Problem Description

King Takahashi of Takahashi Kingdom has decided to install several bus stops to improve transportation within the country. The kingdom has only two types of roads: one running east-west and the other running north-south. The i-th north-south road is laid at the point i kilometers east from a reference point, and the j-th east-west road is laid at the point j kilometers north from the same reference point. The intersection of the i-th north-south road and the j-th east-west road is represented as (i, j). Since the roads are infinitely long, any two perpendicular roads will intersect somewhere. Bus stops can only be installed at intersections, and no more than one bus stop can be installed at the same intersection.

Exactly N bus stops have been installed. However, King Takahashi realizes a significant mistake: the roads are too narrow for buses to turn. This means that each route can only move in one direction, either east-west or north-south. As a result, there are bus stops that cannot be reached by bus. To remedy this inconvenience, additional bus stops will be installed so that any two bus stops can be reached by transferring buses. Note that bus transfers can only occur at bus stops. Moreover, to avoid inconvenience from detours, the total travel distance between any two bus stops should be equal to their Manhattan distance. That is, for any two bus stops (a, b) and (c, d), there should be a transfer route where the total travel distance is |a - c| + |b - d| kilometers.

Due to budget constraints, a total of only 10,000 bus stops can be installed. This means only 10,000 - N more can be installed. Within this limit, determine the locations of the additional bus stops to meet the above conditions. If multiple solutions exist, any one is acceptable.

Input Format

The input is given from the standard input in the following format:

$ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_N $ $ y_N $

• The first line contains an integer $N\ (2\ ≦\ N\ ≦\ 1,000)$, representing the number of bus stops already installed.
• The next $ N $ lines contain two integers each, $x_i\ (1\ ≦\ x_i\ ≦\ 1,000)$ and $y_i\ (1\ ≦\ y_i\ ≦\ 1,000)$, separated by a space, indicating the position of the i-th bus stop at intersection (x_i, y_i).
• It holds that $(x_i, y_i)\ \neq\ (x_j, y_j)$ for $i\ \neq\ j$.
• At least one solution exists.

Output Format

Output the positions of the additional bus stops in the following format:

$ M $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_M $ $ y_M $

• The first line contains an integer $M\ (0\ ≦\ M\ ≦\ 10,000\ -\ N)$, representing the number of new bus stops to be installed.
• The next $ M $ lines contain two integers each, $x_i\ (1\ ≦\ x_i\ ≦\ 1,000)$ and $y_i\ (1\ ≦\ y_i\ ≦\ 1,000)$, separated by a space, indicating the position of the i-th new bus stop at intersection (x_i, y_i).
• It must hold that $(x_i, y_i)\ \neq\ (x_j, y_j)$ for $i\ \neq\ j$.
• The positions of the new bus stops must not overlap with the positions of the already installed bus stops.
• For the combined set of $ N+M $ bus stops, the shortest distance between any two bus stops must be equal to their Manhattan distance.

Sample Input and Output

Sample Input #1

2
1 1
2 2

Sample Output #1

1
1 2

Sample Input #2

4
1 1
2 2
3 4
4 3

Sample Output #2

4
1 2
3 2
3 3
4 4

Sample Input #3

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

Sample Output #3

15
3 6
8 5
2 2
7 5
2 5
6 6
3 1
5 6
6 2
6 1
7 1
7 2
2 3
6 7
2 6

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $2\ ≦\ N\ ≦\ 100$, you will earn 10 points.
• If you correctly solve all test cases where $2\ ≦\ N\ ≦\ 1,000$, you will earn an additional 90 points, totaling 100 points.

Sample Explanation 1

A bus passing through bus stop (1, 1) can only visit (i, 1) or (1, j) (where i, j are any integers). Similarly, a bus passing through bus stop (2, 2) can only visit (i, 2) or (2, j) (where i, j are any integers). Adding a bus stop at (1, 2) allows any two bus stops to be reachable. Note that (2, 1) is also acceptable, and adding both is permissible.

Sample Explanation 2

Be aware that the shortest path between any newly added bus stops must also be equal to their Manhattan distance.

见题面 Input 部分

见题面 Output 部分