D. Рождественские деревья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На бесконечной числовой прямой находятся $$$n$$$ рождественных деревьев. $$$i$$$-е дерево растет на позиции $$$x_i$$$. Гарантируется, что все значения $$$x_i$$$ различны.

Каждая целочисленная точка может быть либо занята рождественским деревом, либо занята человеком, либо не занята вообще. Нецелые точки не могут быть заняты ничем.

Есть $$$m$$$ человек, которые хотят отпраздновать Рождество. Пусть $$$y_1, y_2, \dots, y_m$$$ — это позиции людей (заметьте, что все значения $$$x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$$$ должны быть различны и все $$$y_j$$$ должны быть целыми). Вы хотите найти такое расположение людей, что значение $$$\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$$$ минимально возможное (другими словами, сумма расстояний до ближайшего рождественского дерева по всем людям должна быть минимизирована).

Другими словами, пусть $$$d_j$$$ равно дистанции от $$$j$$$-го человека до ближайшего к нему рождественского дерева ($$$d_j = \min\limits_{i=1}^{n} |y_j - x_i|$$$). Тогда вам надо выбрать такие позиции $$$y_1, y_2, \dots, y_m$$$, что $$$\sum\limits_{j=1}^{m} d_j$$$ минимально возможна.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — количество рождественских деревьев и количество людей.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$), где $$$x_i$$$ равно позиции $$$i$$$-го рождественского дерева. Гарантируется, что все $$$x_i$$$ различны.

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

В первой строке выведите одно целое число $$$res$$$ — минимально возможное значение $$$\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$$$ (другими словами, сумму расстояний до ближайшего рождественского дерева по всем людям).

Во второй строке выведите $$$m$$$ целых чисел $$$y_1, y_2, \dots, y_m$$$ ($$$-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9$$$), где $$$y_j$$$ равно позиции $$$j$$$-го человека. Все $$$y_j$$$ должны быть различными, а еще все значения $$$x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$$$ должны быть различными.

Если существует несколько ответов, выведите любой.

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