D. Объединение k-подотрезков
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано n отрезков на прямой и число k. Будем считать точку на прямой насыщенной, если она принадлежит хотя бы k отрезкам. Найдите набор из наименьшего количества отрезков на прямой, содержащий насыщенные точки и только их.

Входные данные

В первой строке находятся два целых числа n и k (1 ≤ k ≤ n ≤ 106) — количество отрезков и параметр, указанный в условии задачи.

В каждой из следующих n строк находится пара целых чисел li, ri ( - 109 ≤ li ≤ ri ≤ 109) — концы i-го отрезка. Отрезки могут вырождаться в точки, а также могут пересекаться друг с другом произвольным образом. Отрезки заданы в произвольном порядке.

Выходные данные

В первой строке выведите целое число m — наименьшее количество отрезков.

Далее в m строках выведите по два целых числа aj, bj (aj ≤ bj) — концы очередного отрезка. Отрезки нужно выводить в порядке слева направо.

Примеры
Входные данные
3 2
0 5
-3 2
3 8
Выходные данные
2
0 2
3 5
Входные данные
3 2
0 5
-3 3
3 8
Выходные данные
1
0 5