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

Difficulty: introductory

Starter code:

Solutions:
from queue import deque

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

used = set(arr)
q = deque()
for i in range(n):
    q.append([arr[i] - 1, 1, -1])
    q.append([arr[i] + 1, 1, 1])

ret = []
s = 0
while m:
    x, l, dr = q.popleft()
    a = x + dr
    if not a in used:
        q.append([a, l + 1, dr])
    if not x in used:
        used.add(x)
        ret.append(x)
        m -= 1
        s += l
print(s)
print(*ret)

import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
X=list(map(int,input().split()))

SET=set(X)
dis=1

ANS=[]
MSET=set(X)
PSET=set(X)
score=0
MEM=0

while MEM<m:

    REMLIST=[]
    for t in MSET:
        if t-dis in SET:
            REMLIST.append(t)
        else:
            ANS.append(t-dis)
            SET.add(t-dis)
            MEM+=1
            score+=dis

        if MEM==m:
            break

    MSET-=set(REMLIST)

    if MEM==m:
        break

    

    REMLIST=[]
    for t in PSET:
        if t+dis in SET:
            REMLIST.append(t)
        else:
            ANS.append(t+dis)
            SET.add(t+dis)
            MEM+=1
            score+=dis

        if MEM==m:
            break

    PSET-=set(REMLIST)
    dis+=1

print(score)
print(*ANS)

        
            
        


nsap, nhum = map(int, input().split())
ls = list(map(int, input().split()))
sls = set(ls)
candidates = set()
for e in ls:
    if e+1 not in sls:
        candidates.add(e+1)
    if e-1 not in sls:
        candidates.add(e-1)
        
level = 1
totdist = 0
res = set()
while len(res) + len(candidates) <= nhum:
    #print(candidates)
    totdist += level * len(candidates)
    level += 1
    for e in candidates:
        res.add(e)
    cand2 = set()
    for e in candidates:
        for dx in (-1,1):
            if e+dx not in res and e+dx not in sls:
                cand2.add(e+dx)
    candidates = cand2

for i in range(nhum-len(res)):
    res.add(candidates.pop())
    totdist += level

print(totdist)
for e in res:
    print(e, end=' ')


import collections
import heapq
n,m = list(map(int, input().split()))

occupied = set(map(int, input().split()))

q = collections.deque(set([(1, x-1) for x in occupied if x-1 not in occupied] + \
                      [(1, x+1) for x in occupied if x+1 not in occupied]))
for _,x in q:
  occupied.add(x)
ans = []
tot = 0
while len(ans) < m:
  dist, x = q.popleft()
  tot += dist
  ans.append(x)
  if x-1 not in occupied:
    q.append((dist+1, x-1))
    occupied.add(x-1)
  if x+1 not in occupied:
    q.append((dist+1, x+1))
    occupied.add(x+1)
print(tot)
print(' '.join(map(str, ans)))


from collections import deque

n,m = list(map(int,input().split())) #tree/people

x = list(map(int,input().split()))

dic = {}
q = deque([])

d = 0
ans = []

for i in range(n):

    dic[x[i]] = 1

for i in range(n):

    if x[i] - 1 not in dic:
        dic[x[i] - 1] = 1
        q.append([ x[i]-1 , 1 ,"l"])
    if x[i] + 1 not in dic:
        dic[x[i] + 1] = 1
        q.append([ x[i]+1 , 1 ,"r"])

for i in range(m):

    now = q.popleft()

    p = now[0]
    d += now[1]
    direc = now[2]

    ans.append(p)

    if direc == "l":
        if p-1 not in dic:
            dic[p-1] = 1
            q.append([ p-1 , now[1] + 1 , direc ])
    else:
        if p+1 not in dic:
            dic[p+1] = 1
            q.append([ p+1 , now[1] + 1 , direc ])

print (d)
print(" ".join(map(str,ans)))



n, p = list(map(int,input().split()))
l = list(map(int,input().split()))
trees_p = set(l)
trees_l = set(l)
zaj = {}
for i in l:
	zaj[i] = 1
	
dupa = 0
odp = []
odl = 0
import sys
while True:
	odl += 1
	to_rem = []
	for t in trees_l:
		try:
			zaj[t-odl]
			to_rem.append(t)
		except Exception:
			zaj[t-odl] = 1
			odp.append(t-odl)
			dupa += odl
			if len(odp) == p:
				print(dupa)
				print(*odp)
				return
	for x in to_rem:
		trees_l.remove(x)
	
	to_rem = []
	for t in trees_p:
		try:
			zaj[t+odl]
			to_rem.append(t)
		except Exception:
			zaj[t+odl] = 1
			odp.append(t+odl)
			dupa += odl
			if len(odp) == p:
				print(dupa)
				print(*odp)
				return
	for x in to_rem:
		trees_p.remove(x)
			
	



import sys
import collections
from collections import Counter, deque
import itertools
import math
import timeit

#########################
# imgur.com/Pkt7iIf.png #
#########################

def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r

def divs(n, start=1):
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors

def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t

def flin(d, x, default=-1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return (default, default)
    else:
        return (left, right)

def ceil(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return list(map(int, input().split()))
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)

# input = sys.stdin.readline

t = 1
for _ in range(t):
    n, k = mi()
    d = li()
    used = set(d)
    left = d[:]
    right = d[:]
    res = []
    s = 0
    c = 1
    while len(res) < k:
        nl = []
        nr = []
        j = 0
        while len(res) < k and j < len(left):
            if left[j] - 1 not in used:
                s += c
                res.append(left[j] - 1)
                used.add(left[j] - 1)
                nl.append(left[j] - 1)
            j += 1
        j = 0
        while len(res) < k and j < len(right):
            if right[j] + 1 not in used:
                s += c
                res.append(right[j] + 1)
                used.add(right[j] + 1)
                nr.append(right[j] + 1)
            j += 1
        left = nl
        right = nr
        c += 1

    print(s)
    prr(res)


from collections import deque

n, m = list(map(int,input().split()))
queue = deque([])
vst = set()
for k in map(int,input().split()):
    vst.add(k)
    queue.append((k,0))

ans = 0
ans_L = []
cnt = 0

while queue:
    x, step = queue.popleft()
    for dx in [1, -1]:
        X = x + dx
        if X not in vst:
            cnt += 1
            vst.add(X)
            ans += step + 1
            ans_L.append(X)
            queue.append((X, step + 1))
        if cnt == m:
            break
    if cnt == m:
        break

print(ans)
print(*ans_L)






n,m=map(int,input().split())
a=list(map(int,input().split()))
d={}
a.sort()

low=1
high=m

for i in a:
    d[i]=2

from collections import deque

def check(mid,a):
    s=0
    for i in range(n-1):
        s+=min(2*mid,a[i+1]-a[i]-1)
    if s+ 2*mid>=m:
        return True
    else:
        return False
        
    

while low<high:
    mid=(low+high)//2
    if check(mid,a):
        high=mid
    else:
        low=mid+1

st=deque(a)
# print(st)
k=0
ans=[]
pr=0
while m>0:
    if st[0]==a[0]:
        k+=1
        
    if st[0]-k  in d and st[0]+k in d:
        st.popleft()
        continue
    # print(ans)
    if st[0]-k  not in d:
        d[st[0]-k]=1
        m-=1
        pr+=k
        ans.append(st[0]-k)
    # print(ans)    
    if st[0]+k  not in d and m>0:
        d[st[0]+k]=1
        m-=1
        pr+=k
        ans.append(st[0]+k)
    # print(ans)    
    st.append(st.popleft())
    
print(pr)    
print(*ans)        

n, m = list(map(int, input().split()))
trees = set(list(map(int, input().split())))
vis = set(trees)
res = []
dist = 0
for d in range(1, m+1):
    done = False
    removal = set()
    for t in trees:
        if t-d in vis and t+d in vis:
            removal.add(t)
        if not t-d in vis:
            vis.add(t-d)
            res.append(t-d)
            dist += d
        if len(res) == m:
            done = True
            break
        if not t+d in vis:
            vis.add(t+d)
            res.append(t+d)
            dist += d
        if len(res) == m:
            done = True
            break
    if done:
        break
    for t in removal:
        trees.remove(t)
print(dist)
print(' '.join(map(str, sorted(res))))
    
        


import sys
from operator import itemgetter

def input():
    return sys.stdin.readline().strip()

n,m = list(map(int, input().split()))

trees = set(map(int, input().split()))
occ = set(trees)
newadd = set()
for x in trees:
    if x+1 not in occ:
        newadd.add((x+1,1))
    if x-1 not in occ: 
        newadd.add((x-1,1))

anspos = []
ans = 0
while m > 0:
    newnewadd = set()
    while m>0 and len(newadd) > 0:
        x,diff = newadd.pop()
        if x in occ:
            continue
        occ.add(x)
        anspos.append(x)
        ans+=diff
        if x+1 not in occ:
            newnewadd.add((x+1,diff+1))
        if x-1 not in occ:
            newnewadd.add((x-1,diff+1))
        m-=1
    newadd = newnewadd
print(ans)
print(*anspos)

import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	n, m = mints()
	q = list(mints())
	w = dict()
	for i in q:
		w[i] = 0
	ql = 0
	c = 0
	ss = 0
	y = []
	while ql < len(q):
		p = q[ql]
		ql += 1
		x = p - 1
		if x not in w:
			d = w[p] + 1
			y.append(x)
			q.append(x)
			ss += d
			w[x] = d
			c += 1
			if c == m:
				break
		x = p + 1
		if x not in w:
			d = w[p] + 1
			q.append(x)
			y.append(x)
			ss += d
			w[x] = d
			c += 1
			if c == m:
				break
	print(ss)
	print(' '.join(map(str, y)))

#for i in range(mint()):
solve()


import heapq,bisect

def main():
    n,m = map(int,input().split())
    trees = list(map(int,input().split()))
    trees.sort()

    ans = []
    distance = 0
    heap = []
    visited = set()
    for i in trees:
        visited.add(i)

    for i in trees:
        if i+1 not in visited:
            heapq.heappush(heap,(1,i+1))
        if i-1 not in visited:
            heapq.heappush(heap,(1,i-1))

    while heap:
        curr = heapq.heappop(heap)
        if curr[1] not in visited:
            distance += curr[0]
            ans.append(curr[1])
            visited.add(curr[1])
            if len(ans) == m:
                break

            if curr[1]+1 not in visited:
                index = bisect.bisect(trees,curr[1]+1)
                min_dist = float('inf')
                if index < len(trees):
                    min_dist = min(min_dist,trees[index]-curr[1]-1)
                if index-1 >= 0:
                    min_dist = min(min_dist,curr[1]+1-trees[index-1])

                heapq.heappush(heap,(min_dist,curr[1]+1))

            if curr[1]-1 not in visited:
                index = bisect.bisect(trees,curr[1]-1)
                min_dist = float('inf')
                if index < len(trees):
                    min_dist = min(min_dist,trees[index]-curr[1]+1)
                if index-1 >= 0:
                    min_dist = min(min_dist,curr[1]-1-trees[index-1])

                heapq.heappush(heap,(min_dist,curr[1]-1))
        


    print(distance)
    for i in ans:
        print(i,end = ' ')


main()


a = input('').split(' ')
n =int(a[0])
m = int(a[1])
x = list(map(int,input('').split(' ')))
d = {}
for xx in x:
    d[xx] = True

i = 0
c = 0
pos = [[]]
pos.append([])
cur = 0
pos[cur] = x.copy()
ys = []
ans = 0
while(i<m):
    c+=1
    pos[cur^1] = []
    for k in pos[cur]:
        if(k+1 not in d):
            pos[cur^1].append(k+1)
            d[k+1] = True
        if(k-1 not in d):
            pos[cur^1].append(k-1)
            d[k-1] = True
    res = False
    cur = cur^1
    for p in pos[cur]:
        i+=1
        ys.append(p)
        ans += c
        if(i == m):
            res = True
            break
    if(res):
        break

print(ans)
for h in ys:
    print(h,end = ' ')