我们要在一个数轴上绘制 $n$ 个彩色线段。

先绘制的线段可能会被后绘制的线段覆盖。

你的任务是统计最终可以看到的不同颜色的线段。

输入格式

输入包含多组测试数据。

每组数据第一行包含整数 $n$。

接下来 $n$ 行，每行包含三个整数 $l,r,c$，表示绘制左右端点坐标分别为 $l,r$ 的颜色为 $c$ 的线段。

输出格式

每组数据，按照颜色编号从小到大的顺序，每行输出一个最终可以看到的颜色的编号以及该颜色的可见线段数量。

已经完全被覆盖掉的，完全看不到的颜色无需输出。

每组数据输出完毕以后输出一个空行。

数据范围

$1 \le n \le 8000$,
$0 \le l < r \le 8000$,
$0 \le c \le 8000$。

输入样例：

5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1

输出样例：

1 1
2 1
3 1

1 1

0 2
1 1