You are given n segments on the coordinate axis Ox and the number k . The point is satisfied if it belongs to at least k segments. Find the smallest (by the number of segments) set of segments on the coordinate axis Ox which contains all satisfied points and no others.
输入描述:
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 106) — the number of segments and the value of k.The next n lines contain two integers li, ri ( - 109 ≤ li ≤ ri ≤ 109) each — the endpoints of the i-th segment. The segments can degenerate and intersect each other. The segments are given in arbitrary order.
输出描述:
First line contains integer m — the smallest number of segments.Next m lines contain two integers aj, bj (aj ≤ bj) — the ends of j-th segment in the answer. The segments should be listed in the order from left to right.
示例1
输入
3 2<br />0 5<br />-3 2<br />3 8<br />3 2<br />0 5<br />-3 3<br />3 8<br />
输出
2<br />0 2<br />3 5<br />1<br />0 5<br />
加载中...