← 返回题目列表

Codeforces · 612/D

D. k 段的联合

中文机器翻译题面 查看原题

给定坐标轴 Ox 上的 n 段和数字 k。如果该点属于至少 k 个段,则该点满足。找到坐标轴 Ox 上的最小(按线段数量)线段集,其中包含所有满足的点,而不包含其他点。

输入

第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 106) — 段数和 k 的值。

接下来的 n 行包含两个整数 li, ri (- 109 ≤ li ≤ ri ≤ 109) — 第 i 段的端点。这些片段可以退化并相互交叉。这些段以任意顺序给出。

输出

第一行包含整数 m — 最小段数。

接下来 m 行包含两个整数 aj, bj (aj ≤ bj) — 答案中第 j 段的末尾。这些段应按从左到右的顺序列出。

示例

输入 #1

3 2
0 5
-3 2
3 8

输出 #1

2
0 2
3 5

输入 #2

3 2
0 5
-3 3
3 8

输出 #2

1
0 5