207002 - 双关键字排序

试用快速排序法对n对数排序,排序规则为:按照第一个数的升序排序,如果第一个数相等就按照第二个数的升序排序。

Input

第一行输入一个整数n(1≤n≤100 000)。 接下来n行每行输入一对整数ai,bi(1≤ai,bi≤10 000)。

Output

按照升序输出所有整数对。

Examples

Input

4
2 4
1 3
1 2
2 3

Output

1 2
1 3
2 3
2 4
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题