题目描述

给定n个闭区间 [ai,bi], i=1，2，…n。 这些区间的和可以用两两不相交的闭区间的和来表示。你的任务是找到这样的区间数目最少的表示，且把它们按升序的方式写到输出文件中。当且仅当a≤b<c≤d时，区间[a,b]、[c,d]才是升序

输入格式

输入文件的第一行只有一个数n（3≤n≤50000），代表区间数； 接下来n行，每行有两个空间隔开的整数ai、bi，表示区间[ai,bi]的起始和结束（1≤i≤n，1≤ai≤bi≤1000000）。

输出格式

按升序输出所有的区间，每行写一个区间，每行只有两个数，分别是区间起始和结束。

样例

5 
5 6 
1 4
10 10
6 9
8 10

1 4
5 10