题目描述

给定 $n$ 个区间，其中第 $i$ 个区间可以表示为 $[l_i, r_i]$。

现在你需要将这 $n$ 个区间进行排序。排序的规则如下：

• 优先按照区间的右端点 $r_i$ 从小到大进行排序；
• 如果右端点相同，则按照左端点 $l_i$ 从小到大进行排序。

请输出排序后的所有区间。

输入格式

第一行包含一个正整数 $n$，表示区间的数量。

接下来 $n$ 行，每行包含两个正整数 $l_i, r_i$ —— 分别表示第 $i$ 个区间的左端点和右端点。

输出格式

输出 $n$ 行，每行包含两个正整数，表示排序后的区间。

样例输入 1

5
2 5
1 5
3 4
1 2
4 6

样例输出 1

1 2
3 4
1 5
2 5
4 6

说明

样例解释

在样例中，区间的右端点从小到大排序为 $2, 4, 5, 5, 6$。 其中有两个区间的右端点同为 $5$，分别是 $[2, 5]$ 和 $[1, 5]$，由于规则规定右端点相同时按左端点从小到大排序，因此 $[1, 5]$ 排在 $[2, 5]$ 的前面。

数据范围

对于所有测试点，保证

• $1 \le n \le 2 \times 10^5$，
• $1 \le l_i \le r_i \le 10^9$。