Peatown 已经成为一个大都市。我们可以将其看作一个矩形街道网格。有 50,000 条南北走向的垂直街道（用 $x$ 坐标标记，范围从 1 到 50,000）和 50,000 条东西走向的水平街道（用 $y$ 坐标标记，范围从 1 到 50,000）。所有街道都是双向车道。水平街道和垂直街道的交汇处称为十字路口。

Peatown 的居民非常不负责任且鲁莽。他们开车像疯子一样，因此 Peatown 的市长决定在 $N$ 个十字路口设置红绿灯。如果两个十字路口之间的路径中存在没有红绿灯的转弯，则该路径是危险的。否则，它是安全的。

要确保所有路径都是安全的是不可能的，但如果任意两个红绿灯之间至少有一条最短路径是安全的，Peatown 的市长就会感到满意。不幸的是，目前红绿灯的分布太危险了。你的任务是放置额外的红绿灯（少于 700,000 个），使得红绿灯的集合（包含新旧红绿灯）满足市长的要求。相信你一定很聪明，快来帮助 Peatown 的居民吧！

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 50\,000$)，表示初始放置的红绿灯数量。

接下来的 $N$ 行，每行包含一个红绿灯的位置，用整数 $X$ 和 $Y$ ($1 \le X, Y \le 50\,000$) 表示，即相交于该十字路口的垂直街道和水平街道的坐标。所有初始红绿灯的位置都是互不相同的。

输出格式

输出新红绿灯的位置，每行一个。

允许在同一个位置放置多个红绿灯。

新红绿灯的数量必须小于 700,000。

样例

输入样例 1

2
1 1
3 3

输出样例 1

1 3

输入样例 2

3
2 5
5 2
3 3

输出样例 2

3 5
5 3

输入样例 3

5
1 3
2 5
3 4
4 1
5 2

输出样例 3

1 5
3 3
3 5
4 2
4 3