弹幕是现今网络视频常见的评论方式,能够反映一个视频的火爆程度。假设某个时间一共有N条弹幕,每条弹幕i的持续时间为两个整数表示的时间区间(a[i],b[i]),我们定义弹幕数量最多的一个时间段为最精彩时段,求一个视频的最精彩时段。
输入描述:
第一行整数N,代表弹幕的条数,其中90%的 N 第二行到第N+1行,是两个整数(a[i],b[i]),代表每条弹幕的开始时间和结束时间, 请注意(a[i],b[i])是全开区间, 并且a[i], b[i] 100


输出描述:
M行,每行两个整数(c,d),M是答案个数,(c,d)代表视频最精彩时段的开始时间和结束时间,并且M个答案区间互不重叠。答案请按照开始时间从小到大输出。请注意每行结尾应包含换行符,包括最后一行。
示例1

输入

3
0 4
1 4
2 3

输出

2 3
示例2

输入

4
1 2
3 4
2 3
4 5

输出

1 2
2 3
3 4
4 5
示例3

输入

3
0 2
2 4
1 3

输出

1 2
2 3

说明

请注意由于区间定义为开区间,所以答案为(1,2)和(2,3)
加载中...