Problem Description

There are many streets crisscrossing each other, all of which are bidirectional. The intersections of horizontal and vertical streets are called crossroads.

It has been decided to install traffic lights at $N$ crossroads. Turning is dangerous on a road between two crossroads if there are no traffic lights, and safe otherwise.

The requirement is met if there is at least one shortest path that is safe between every pair of traffic lights. You need to set up additional traffic lights to meet this requirement.

Input Format

The first line of input consists of an integer $N$, the initial number of traffic lights.

The next $N$ lines each contain two integers $x_i$ and $y_i$, representing the coordinates of the $i$-th traffic light.

All coordinates of the traffic lights are distinct.

Output Format

Output the positions of the new traffic lights. Multiple traffic lights can be placed at the same position, but the number of additional traffic lights must be less than $7 \times 10^5$.

Sample Input and Output

Sample Input #1

2
1 1
3 3

Sample Output #1

1 3

Sample Input #2

3
2 5
5 2
3 3

Sample Output #2

3 5
5 3

Sample Input #3

5
1 3
2 5
3 4
4 1
5 2

Sample Output #3

1 5
3 3
3 5
4 2
4 3

Notes

Data Constraints

• $2 \leq N \leq 5 \times 10^4$.
• $1 \leq x_i, y_i \leq 5 \times 10^4$.

Notes

Translated from COCI2013-2014 CONTEST #6 T6 GRAŠKRIŽJA.

见题面 Input 部分

见题面 Output 部分