Description

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

写一个程序完成以下任务：

●从prz.in中读取区间

●计算出满足上述条件的两两不相交的区间

●把找到的区间按升序写入到prz.out中

Input Format

输入文件prz.in的第一行只有一个数n，3<=n<=50000，代表区间数。第I+1行有两个数ai,bi,之间用一个空格隔开，分别表示区间[ai,bi]的起始和结束（1<=i<=n,1<=ai<=bi<= 1000000）

Output Format

输出文件prz.out应该包含计算出的所有区间，每行写一个区间，每行只有两个数，分别是区间起始和结束，之间用一个空格分开。记住必须是按升序输出。

Sample

【输入样例】 5 5 6 1 4 10 10 6 9 8 10 【输出样例】 1 4 5 10