给定坐标轴 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