문제

Author: Luka Kalinovčić, Adrian Satja Kurdija

Peatown has become a metropolis. We can observe it as a rectangular grid of streets. There are fifty thousand vertical streets running north-south (labeled with x-coordinates from 1 to 50 000) and fify thousand horizontal streets running east-west (labeled with y-coordinates from 1 to 50 000). All streets are two-way streets. An intersection of a horizontal and vertical street is called a crossroads. Residents of Peatown are very irresponsible and reckless. They drive like idiots so the mayor of Peatown has decided to place traffic lights on N crossroads. A path between two crossroads is dangerous if there is a turn without a traffic light. Otherwise it is harmless. It is not possible to ensure that all paths are harmless, but the mayor of Peatown is satisfied if between each two traffic lights at least one of the shortest paths is harmless. Unfortunately, the current distribution of traffic lights is too dangerous. Your task is to place additional traffic lights (less than 700 000 of them) so that the set of traffic lights (which contains both new and old traffic lights) meets the mayor's requirement. Surely you're not pea-brained so help the residents of Peatown!

입력

The first line of input consists of an integer N (2 ≤ N ≤ 50 000), the number of initially placed traffic lights. Each of the following N lines contains a location of one traffic light, represented with integers X and Y (1 ≤ X, Y ≤ 50 000), coordinates of the vertical and horizontal streets which intersect in that crossroads. All traffic lights will be unique.

출력

Output the locations of new traffic lights, each in its own line. Placing multiple traffic lights on the same location is allowed. The number of new traffic lights must be smaller than 700 000.

예제 입력 1

2
1 1
3 3

예제 출력 1

1 3

예제 입력 2

3
2 5
5 2
3 3

예제 출력 2

3 5
3 2

예제 입력 3

5
1 3
2 5
3 4
4 1
5 2

예제 출력 3

3 3
3 5
3 1
3 2
1 5
4 2