Background

我令死亡不再是「均衡」的终点——遐蝶

愿「生死」萌发新蕊

Description

某天，遐蝶在模拟宇宙里打到了最终BOSS，发现最终BOSS竟然有 $5$ 亿血量，凭借现在的自己肯定是无法战胜，必须要想办法提升自己。

在重来之后的某一关，她遇到了啊哈，啊哈给了她一个道题目，如果她可以正确解答这道题目，就会获得神力，战胜BOSS。

这道题是这样的：给你 $n$ 个数轴上的区间，每个区间有三个参数 $a_i, b_i, c_i$，分别表示区间的范围是 $[a_i, b_i]$，区间的权值为 $c_i$。

她的任务是这样的：

1. 将这些区间按照左端点从小到大排序。
2. 将这些区间的重叠部分转换为新的区间，区间权值为重叠区间中较小的权值，如区间 $([1, 3], 2)$ 和区间 $([2, 4], 1)$ 的重叠部分为 $([2, 3], 1)$ (范围为 $[2, 3]$，较小的权值为 $1$)，因此变为三个区间：$([1, 2], 2), ([2, 3], 1), ([3, 4], 1)$。
3. 将相连且权值相等的区间合并，如上面的例子应该将 $([2, 3], 1), ([3, 4], 1)$ 合并为 $([2, 4], 1)$。

请你帮她完成这道题目。

Format

Input

第一行输入一个整数 $n \ (1 \le n \le 10^5)$，表示区间数量。

接下来 $n$ 行每行输入三个空格分隔的整数 $a_i, b_i, c_i \ (1\le i\le n, 0 \le a_i < b_i \le 10^9, 1 \le c_i \le 10^9)$，分别表示区间左端点为 $a_i$，区间右端点为 $b_i$，区间权值为 $c_i$。

Output

每行输出三个空格分隔的整数，分别表示区间的左端点、右端点和权值。

你输出的区间需要满足：

• 按左端点升序排序。
• 没有重叠部分。
• 没有两个相邻的区间有相同的权值。
• 区间长度不能为 $0$，即区间端点不相等。

Samples

2
1 3 1
2 4 2

1 3 1
3 4 2

2
1 3 2
2 4 1

1 2 2
2 4 1

3
2 3 1
3 4 1
1 5 2

1 2 2
2 4 1
4 5 2

3
2 3 2
3 4 2
1 5 1

1 5 1