楼房

题目描述

地平线($x$ 轴)上有 $n$ 个楼房,每个楼房可以表示为一个矩形。 用三个整数 $h_i,l_i,r_i$ 来表示第 $i$ 个矩形:矩形左下角为 $(l_i,0)$,右上角为 $(r_i,h_i)$。 地平线高度为 $0$。在轮廓线长度最小的前提下,从左到右输出轮廓线。

输入输出格式

输入格式


第一行一个整数 $n$,表示矩形个数。 以下 $n$ 行,每行 $3$ 个整数 $h_i,l_i,r_i$ 表示第 $i$ 个矩形。

输出格式


第一行一个整数 $m$,表示节点个数。 以下 $m$ 行,每行一个坐标表示轮廓线上的节点。 要求从左到右遍历轮廓线并顺序输出节点。 注:第一个和最后一个节点的 $y$ 坐标必然为 $0$。

输入输出样例

输入样例 #1

2
3 0 2
4 1 3

输出样例 #1

6
0 0
0 3
1 3
1 4
3 4
3 0

输入样例 #2

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8

输出样例 #2

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0

说明

样例二如图: ![](https://cdn.luogu.com.cn/upload/pic/176.png) 数据范围: 对于 $30\%$ 的数据,$n\le100$。 对于另外 $30\%$ 的数据,$1\le h_i,l_i,r_i\le 1000$。 对于 $100\%$ 的数据,$1\le n\le10^5$,$1\le h_i\le 10^9$,$-10^9\le l_i<r_i\le10^9$。