Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

D. Christmas Trees
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $n$ Christmas trees on an infinite number line. The $i$-th tree grows at the position $x_i$. All $x_i$ are guaranteed to be distinct.

Each integer point can be either occupied by the Christmas tree, by the human or not occupied at all. Non-integer points cannot be occupied by anything.

There are $m$ people who want to celebrate Christmas. Let $y_1, y_2, \dots, y_m$ be the positions of people (note that all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct and all $y_j$ should be integer). You want to find such an arrangement of people that the value $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ is the minimum possible (in other words, the sum of distances to the nearest Christmas tree for all people should be minimized).

In other words, let $d_j$ be the distance from the $j$-th human to the nearest Christmas tree ($d_j = \min\limits_{i=1}^{n} |y_j - x_i|$). Then you need to choose such positions $y_1, y_2, \dots, y_m$ that $\sum\limits_{j=1}^{m} d_j$ is the minimum possible.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of Christmas trees and the number of people.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($-10^9 \le x_i \le 10^9$), where $x_i$ is the position of the $i$-th Christmas tree. It is guaranteed that all $x_i$ are distinct.

Output

In the first line print one integer $res$ — the minimum possible value of $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ (in other words, the sum of distances to the nearest Christmas tree for all people).

In the second line print $m$ integers $y_1, y_2, \dots, y_m$ ($-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9$), where $y_j$ is the position of the $j$-th human. All $y_j$ should be distinct and all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct.

If there are multiple answers, print any of them.

Examples
Input
2 6
1 5

Output
8
-1 2 6 4 0 3

Input
3 5
0 3 1

Output
7
5 -2 4 -1 2