Dreamoon likes coloring cells very much.

There is a row of $n$ cells. Initially, all cells are empty (don't contain any color). Cells are numbered from $1$ to $n$.

You are given an integer $m$ and $m$ integers $l_1, l_2, \ldots, l_m$ ($1 \le l_i \le n$)

Dreamoon will perform $m$ operations.

In $i$-th operation, Dreamoon will choose a number $p_i$ from range $[1, n-l_i+1]$ (inclusive) and will paint all cells from $p_i$ to $p_i+l_i-1$ (inclusive) in $i$-th color. Note that cells may be colored more one than once, in this case, cell will have the color from the latest operation.

Dreamoon hopes that after these $m$ operations, all colors will appear at least once and all cells will be colored. Please help Dreamoon to choose $p_i$ in each operation to satisfy all constraints.


-----Input-----

The first line contains two integers $n,m$ ($1 \leq m \leq n \leq 100\,000$).

The second line contains $m$ integers $l_1, l_2, \ldots, l_m$ ($1 \leq l_i \leq n$).


-----Output-----

If it's impossible to perform $m$ operations to satisfy all constraints, print "'-1" (without quotes).

Otherwise, print $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \leq p_i \leq n - l_i + 1$), after these $m$ operations, all colors should appear at least once and all cells should be colored.

If there are several possible solutions, you can print any.


-----Examples-----
Input
5 3
3 2 2

Output
2 4 1

Input
10 1
1

Output
-1

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms


Solutions:
(n, m, *l) = map(int, open(0).read().split())
if sum(l) < n or any((i + x > n for (i, x) in enumerate(l))):
	print(-1)
	exit()
for i in range(m - 1):
	l[-i - 2] += l[-i - 1]
print(*[max(i + 1, n - l[i] + 1) for i in range(m)])


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
if sum(arr) < n:
	print(-1)
	exit()
ans = []
p = n + 1
for c in arr[::-1]:
	p = min(p - 1, n + 1 - c)
	ans.append(p)
ans = ans[::-1]
if ans[0] < 1:
	print(-1)
	exit()
if ans[0] > 1:
	pos = 1
	for (i, c) in enumerate(arr):
		ans[i] = min(ans[i], pos)
		pos = pos + c
print(*ans)


def main():
	(n, m) = readIntArr()
	l = readIntArr()
	p = [0 for _ in range(m)]
	left = 1
	ok = True
	for i in range(m):
		right = l[i] + left - 1
		if right > n:
			ok = False
			break
		p[i] = left
		left += 1
	if ok:
		furthestRightCovered = n + 1
		for i in range(m - 1, -1, -1):
			newLeft = furthestRightCovered - 1 + 1 - l[i]
			p[i] = max(p[i], newLeft)
			furthestRightCovered = p[i]
		if p[0] == 1:
			oneLineArrayPrint(p)
		else:
			print(-1)
	else:
		print(-1)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
main()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
p = []
paint_remaining = sum(l)
if paint_remaining < n or len(l) + l[len(l) - 1] - 1 > n:
	print(-1)
else:
	firstindex = 1
	p.append(1)
	paint_remaining -= l[0]
	failed = False
	for paint_length in l[1:]:
		if n - firstindex > paint_remaining:
			firstindex = n - paint_remaining + 1
		else:
			firstindex += 1
			if firstindex + paint_length - 1 > n:
				print(-1)
				failed = True
				break
		paint_remaining -= paint_length
		p.append(firstindex)
	if not failed:
		print(*p)


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	if sum(a) < n or m - 1 + a[-1] > n:
		print(-1)
		exit()
	pos = list(range(1, m)) + [n - a[-1] + 1]
	for i in range(m - 2, -1, -1):
		pos[i] = min(pos[i], n - a[i] + 1, pos[i + 1] - 1)
		if pos[i] + a[i] < pos[i + 1]:
			pos[i] = min(n - a[i] + 1, pos[i + 1] - a[i])
	if min(pos) < 1:
		print(-1)
	else:
		print(*pos)
main()


(n, m) = map(int, input().split())
array = list(map(int, input().split()))
ans = 0
if sum(array) < n:
	ans = -1
for i in range(m):
	if array[i] > n - i:
		ans = -1
		break
if ans == -1:
	print(-1)
else:
	sufix_array = [0] * m
	sufix_array[-1] = array[-1]
	for i in range(m - 2, -1, -1):
		sufix_array[i] = array[i] + sufix_array[i + 1]
	for i in range(m):
		print(max(i + 1, n - sufix_array[i] + 1), end=' ')
	print()


from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
x = sum(l)
if x < n:
	print(-1)
else:
	dasie = True
	for i in range(m):
		if l[i] > n - i:
			dasie = False
	if not dasie:
		print(-1)
	else:
		odp = [1]
		cyk = 1
		while cyk < m:
			x -= l[cyk - 1]
			odp.append(max(odp[-1] + 1, n + 1 - x))
			cyk += 1
		print(*odp)


(n, m) = list(map(int, input().split()))
l = list(map(int, input().split()))
ind = 0
for i in range(m):
	if n - l[i] < i:
		ind = 1
if ind == 1:
	print(-1)
elif sum(l) < n:
	print(-1)
else:
	over = sum(l) - n
	i = 0
	while over > 0:
		if i < m:
			k = l[i] - 1
			l[i] -= min(over, l[i] - 1)
			over -= min(over, k)
			i += 1
	place = [1]
	inc = 1 + l[0]
	for i in range(1, m):
		place.append(inc)
		inc += l[i]
	print(' '.join(list(map(str, place))))


from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
larr = list(map(int, input().split()))
for (i, l) in enumerate(larr):
	if l > n - i:
		print(-1)
		exit(0)
sl = sum(larr)
if sl < n:
	print(-1)
	exit(0)
ps = []
for (i, l) in enumerate(larr):
	if sl > n - i:
		ps.append(i + 1)
	else:
		ps.append(n - sl + 1)
	sl -= l
print(*ps)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
if sum(l) < n:
	print(-1)
else:
	flag = False
	for i in range(m):
		if l[i] + i > n:
			flag = True
	if flag:
		print(-1)
	else:
		ans = []
		suff = []
		s = 0
		l.reverse()
		for i in l:
			s += i
			suff.append(s)
		suff.reverse()
		for i in range(m):
			ans.append(max(i + 1, n - suff[i] + 1))
		for i in ans:
			print(i, end=' ')
		print()


import sys
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
pos = [0 for i in range(m)]
upd = [0 for i in range(m)]
cur = 1
for i in range(m):
	pos[i] = cur
	cur += l[i]
diff = pos[m - 1] - (n - l[i] + 1)
if diff < 0:
	print(-1)
	sys.exit()
if diff > 0:
	for i in range(1, m):
		shift = pos[i] - pos[i - 1] - 1
		upd[i] -= min(shift, diff)
		diff -= min(shift, diff)
		if diff == 0:
			break
val = 0
for i in range(m):
	val += upd[i]
	pos[i] += val
for i in range(m):
	if pos[i] > n - l[i] + 1:
		print(-1)
		sys.exit()
for i in range(1, m):
	if pos[i] == pos[i - 1]:
		print(-1)
		sys.exit()
print(*pos)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
if sum(l) < n:
	print(-1)
else:
	f = 0
	i = 0
	dif = sum(l) - n
	end = 1
	a = [1]
	for i in range(m):
		leg = l[i]
		if leg > n - i:
			f = 1
			break
		if dif >= leg:
			end += 1
			dif -= leg - 1
		else:
			end += leg - dif
			dif = 0
		a.append(end)
	if f == 1:
		print(-1)
	else:
		a.pop()
		print(*a)


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

def solve():
	if s < n:
		return [-1]
	for i in range(m):
		if l[i] > n - i:
			return [-1]
	ov = s - n
	idx = 1
	sln = []
	for i in range(m):
		if ov > 0 and idx != 1:
			d = min(ov, l[i - 1] - 1)
			idx -= d
			ov -= d
		sln.append(idx)
		idx += l[i]
	return sln
print(*solve())


import sys
from math import sqrt, floor, factorial
from collections import deque, Counter
inp = sys.stdin.readline
read = lambda : list(map(int, inp().strip().split()))

def solve():
	ans = ''
	(n, m) = read()
	arr = read()
	d = sum(arr) - n
	if d >= 0:
		ind = 1
		for i in arr:
			if n - i + 1 >= ind:
				ans += str(ind) + ' '
				sub = max(1, i - d)
				ind += sub
				d -= i - sub
			else:
				ans = '-1'
				break
	else:
		ans = '-1'
	print(ans)
solve()


def main():
	(N, M) = [int(x) for x in input().split()]
	L = [int(x) for x in input().split()]
	if sum(L) < N or any(map(lambda e: e[1] > N - e[0], enumerate(L))):
		print(-1)
		return
	S = [i + 1 for i in range(M)]
	S[M - 1] = N - L[M - 1] + 1
	for i in reversed(range(M - 1)):
		S[i] = max(S[i], S[i + 1] - L[i])
	print(' '.join(map(lambda s: str(s), S)))
	return
main()


def go():
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	if sum(x) < n:
		return -1
	for (i, xx) in enumerate(x):
		if i + xx > n:
			return -1
	res = list(range(1, 1 + m))
	right = max((a + b - 1 for (a, b) in zip(x, res)))
	if right < n:
		mis = n - (x[-1] + m - 1)
		plus = [0] * m
		i = m - 2
		while mis > 0:
			plus[i + 1] = min(mis, x[i] - 1)
			mis -= plus[i + 1]
			i -= 1
		for i in range(1, m):
			plus[i] += plus[i - 1]
			res[i] += plus[i]
	return ' '.join(map(str, res))
t = 1
for _ in range(t):
	print(go())


(n, m) = map(int, input().strip().split())
ops = list(map(int, input().strip().split()))
if sum(ops) < n:
	print(-1)
else:
	ans = 1
	pos = [0 for j in range(m)]
	for j in range(m):
		if n - j >= ops[j]:
			pos[j] = j
		else:
			ans = 0
			break
	if ans == 0:
		print(-1)
	else:
		max_end = n - 1
		for j in range(m - 1, 0, -1):
			en1 = pos[j] + ops[j] - 1
			if en1 < max_end:
				pos[j] = pos[j] + max_end - en1
				max_end = pos[j] - 1
			else:
				break
		for j in range(m):
			print(pos[j] + 1, end=' ')


from sys import stdin
import copy
input = stdin.readline
(n, m) = map(int, input().split())
l = [int(x) for x in input().split()]
ll = copy.copy(l)
res = [1]
flag = 1
s = sum(l)
if s < n:
	print(-1)
else:
	k = s - n
	start = 1
	for x in range(m):
		if l[x] > 1:
			if l[x] - 1 >= k:
				l[x] -= k
				break
			else:
				k -= l[x] - 1
				l[x] = 1
	for x in l[:-1]:
		res.append(start + x)
		start += x
	for x in range(m):
		if res[x] + ll[x] - 1 > n:
			flag = 0
			break
	if flag == 0:
		print(-1)
	else:
		for x in res:
			print(x, end=' ')


def solve(n, m, li):
	pi = [0] * (m + 1)
	if sum(li) < n:
		print(-1)
		return
	for i in range(1, m + 1):
		if i > n - li[i] + 1:
			print(-1)
			return
		pi[i] = i
	last_pos = n
	for i in range(m, 0, -1):
		while pi[i] + li[i] - 1 < last_pos:
			pi[i] += 1
		last_pos = pi[i] - 1
	print(*pi[1:])
	return
(n, m) = [int(x) for x in input().split()]
li = [0] + [int(x) for x in input().split()]
solve(n, m, li)


(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
for i1 in range(m):
	if i1 > n - p[i1]:
		print(-1)
		exit()
if sum(p) < n:
	print(-1)
	exit()
position = [-1] * m
greedy = 0
for i1 in range(m - 1, -1, -1):
	greedy += p[i1]
	position[i1] = max(i1 + 1, n - greedy + 1)
print(*position)


(n, m) = map(int, input().split())
l = [int(_) for _ in input().split()]
sum = 0
for i in l:
	sum += i
if sum < n:
	print(-1)
	exit(0)
for i in range(m):
	if n - l[i] < i:
		print(-1)
		exit(0)
p = [0] * (m + 1)
p[m] = n
for i in range(m - 1, -1, -1):
	p[i] = max(i, p[i + 1] - l[i])
for i in range(m):
	print(p[i] + 1, end=' ')


def build(s, l):
	for i in range(m - 1, -1, -1):
		s[i] = s[i + 1] + l[i]

def process(s, l, ok):
	ans = []
	left = 1
	for i in range(m):
		ans.append(left)
		nxt = max(left + 1, n - s[i + 1] + 1)
		if nxt > left + l[i]:
			ok = False
			return []
		left = nxt
	return ans
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
s = [0] * (m + 1)
build(s, l)
ok = bool(False)
for i in range(m):
	if n - l[i] < i:
		ok = True
if s[0] < n:
	ok = True
ans = process(s, l, ok)
if len(ans) == 0:
	ok = True
if ok:
	print(-1)
else:
	print(' '.join(map(str, ans)))


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	(n, m) = LI()
	l = LI()
	s = sum(l)
	if s < n:
		print(-1)
		return
	res = s - n
	ans = [1]
	j = 1
	for i in range(1, m):
		r = l[i - 1] - 1
		if res >= r:
			j += 1
			res -= r
		else:
			j += r - res + 1
			res = 0
		if j + l[i] - 1 > n:
			print(-1)
			return
		ans.append(j)
	print(*ans)
	return
solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
vals = list(map(int, input().split()))
broke = False
mcover = 0
ans = []
prefcover = []
for s in range(m):
	if s + 1 <= n - vals[s] + 1:
		mcover = max(mcover, s + vals[s])
		ans.append(s + 1)
		prefcover.append(mcover)
	else:
		broke = True
		break
if broke == True:
	print(-1)
else:
	diff = n - mcover
	shift = []
	for s in range(1, m):
		if diff == 0:
			break
		else:
			avl = prefcover[s - 1] - s
			v0 = min(avl, diff)
			diff -= v0
			shift.append(v0)
	if len(shift) > 0:
		prefsum = [0, shift[0]]
		for s in range(1, len(shift)):
			prefsum.append(prefsum[-1] + shift[s])
		for s in range(1, m):
			if s <= len(prefsum) - 1:
				ans[s] += prefsum[s]
			else:
				ans[s] += prefsum[-1]
	if diff == 0:
		ans[-1] = n - vals[-1] + 1
		print(*ans)
	else:
		print(-1)


(n, m) = map(int, input().split())
l = [int(i) for i in input().split()]
pref = [0]
for i in range(m):
	pref += [pref[-1] + l[i]]
if pref[-1] < n:
	print(-1)
else:
	last_pos = 0
	poss = 0
	ans = [0]
	for i in range(m):
		if ans[-1] + l[i] > n:
			print(-1)
			exit()
		poss = last_pos - ans[-1]
		left = pref[-1] - pref[i] - (n - last_pos)
		if left >= poss:
			ans += [ans[-1] + 1]
		else:
			ans += [ans[-1] + poss - left + 1]
		last_pos = max(last_pos, ans[-1] + l[i] - 1)
	print(*ans[1:])


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
ans = [i + 1 for i in range(m)]
ans.append(n + 1)
for i in range(m - 1, -1, -1):
	ans[i] += max(0, ans[i + 1] - ans[i] - l[i])
res = True
ans[m] = 0
l.append(1)
for i in range(m):
	if not 1 <= ans[i] - ans[i - 1] <= l[i - 1]:
		res = False
		break
	if ans[i] > n - l[i] + 1:
		res = False
		break
if res:
	print(*ans[:m])
else:
	print(-1)


(n, m) = map(int, input().split())
li = list(map(int, input().split()))
sumli = sum(li)
if sumli < n:
	print(-1)
else:
	deficiency = n - m
	for i in range(m):
		if i + li[i] > n:
			print(-1)
			break
	else:
		i = n - li[-1]
		deficiency -= li[-1] - 1
		output = [i]
		z = m - 2
		while deficiency > 0:
			deficiency -= li[z] - 1
			if deficiency >= 0:
				output.append(output[-1] - li[z])
			else:
				output.append(output[-1] - deficiency - li[z])
			z -= 1
		for i in range(z, -1, -1):
			output.append(i)
		output.reverse()
		output = list(map(lambda i: i + 1, output))
		print(*output)


def f():
	n = int(input().split()[0])
	l = [int(x) for x in input().split()]
	s = 0
	for i in l:
		s += i
	if s < n:
		print(-1)
		return
	o = s - n
	b = 0
	u = '1'
	p = 0
	for i in range(0, len(l) - 1):
		if l[i] - 1 < o:
			p = b + 2
			b += 1
			o -= l[i] - 1
		elif o == 0:
			p = b + l[i] + 1
			b += l[i]
		else:
			p = b + l[i] - o + 1
			b += l[i] - o
			o = 0
		if b + l[i + 1] > n:
			print(-1)
			return
		u += ' ' + str(p)
	print(u)
f()


(n, m) = [int(s) for s in input().split()]
arr = [int(s) for s in input().split()]
suf = [0] * m
sum = 0
for i in range(len(arr) - 1, -1, -1):
	sum += arr[i]
	suf[i] = sum
ans = [0] * m
flag = True
for i in range(len(arr)):
	if arr[i] + i > n:
		flag = False
		break
	ans[i] = max(i + 1, n - suf[i] + 1)
	if i != 0:
		if ans[i] <= ans[i - 1]:
			flag = False
			break
if flag and sum >= n:
	for i in ans:
		print(i, end=' ')
else:
	print(-1)


(n, m) = map(int, input().split())
lis = list(map(int, input().split()))
p = []
for i in range(m):
	if lis[i] + i <= n:
		p.append(i + 1)
	else:
		print('-1')
		break
else:
	var = 0
	if p[-1] + lis[-1] < n + 1:
		var = n + 1 - p[-1] - lis[-1]
		las = n
		for j in range(1, m):
			p[-j] = las - lis[-j] + 1
			las = p[-j] - 1
			var -= lis[-j - 1] - 1
			if var <= 0:
				break
	if sum(lis) < n:
		print(-1)
	elif var > 0:
		print(-1)
	else:
		for j in p:
			print(j, end=' ')
		print()


def indexer(x, y, n):
	if x > y:
		return n - x + 1
	else:
		return n - y

def repair(ans, n, z):
	if n == 0:
		return
	push = [0 for i in range(len(ans))]
	for i in range(len(ans) - 2, -1, -1):
		z[i] = z[i] - (ans[i + 1] - ans[i])
		while n > 0 and z[i] > 0:
			n -= 1
			push[i] += 1
			z[i] -= 1
	if n > 0:
		ans[0] = -1
		return ans
	for i in range(len(push) - 1, -1, -1):
		ans[i] -= push[i]
		if i != 0:
			push[i - 1] += push[i]
	return ans
(n, k) = map(int, input().split())
z = list(map(int, input().split()))
if sum(z) < n:
	print(-1)
	exit(0)
gns = 0
flag = 0
ans = [0 for i in range(len(z))]
for i in range(len(z) - 1, -1, -1):
	if gns == n:
		flag = 1
		break
	ans[i] = indexer(z[i], gns, n)
	gns = n - ans[i] + 1
if flag == 1:
	print(-1)
	exit(0)
repair(ans, n - gns, z)
if ans[0] == -1:
	print(-1)
	exit(0)
print(*ans)


import sys
import heapq
(n, m) = map(int, sys.stdin.readline().split())
list_cell = list(map(int, sys.stdin.readline().split()))
now_sum = 0
error = 0
for (i, num) in enumerate(list_cell):
	now_sum += num
	if num + i > n:
		error = 1
if now_sum < n or error:
	print(-1)
else:
	now_index = 0
	list_result = []
	now_x = 0
	next_index = 1
	for now_index in range(m):
		list_result.append(next_index)
		if list_cell[now_index] >= 2 and now_sum > n:
			if now_sum - n <= list_cell[now_index] - 1:
				list_cell[now_index] -= now_sum - n
				next_index += list_cell[now_index]
				now_sum -= now_sum - n
			else:
				now_sum -= list_cell[now_index] - 1
				list_cell[now_index] = 1
				next_index += list_cell[now_index]
		else:
			next_index += list_cell[now_index]
	print(*list_result)


def res():
	print(-1)
	exit()
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
idx = []
if sum(l) < n:
	res()
else:
	for i in range(m):
		if i + l[i] > n:
			res()
	for i in range(m - 1, -1, -1):
		if n > min(i, m - 1 - i):
			curr = min(n - i, l[i])
			idx.append(n - curr + 1)
			n -= curr
		else:
			idx.append(n)
			n -= 1
	print(*idx[::-1])


(n, m) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
suf_sum = [0 for _ in range(m)]
suf_sum[-1] = l[-1]
for i in range(m - 2, -1, -1):
	suf_sum[i] = suf_sum[i + 1] + l[i]
if sum(l) < n:
	print(-1)
else:
	done = False
	for i in range(m):
		if l[i] + i > n:
			print(-1)
			done = True
			break
	if not done:
		p = [None for _ in range(m)]
		for i in range(m):
			p[i] = max(i, n - suf_sum[i])
		print(' '.join([str(_ + 1) for _ in p]))


(n, m) = map(int, input().split())
b = [int(a) for a in input().split()]
if sum(b) < n:
	print(-1)
else:
	s = n + 1
	r = [-1] * m
	i = 0
	for j in b[::-1]:
		s = max(s - j, m - i)
		if s + j - 1 > n:
			print(-1)
			break
		r[i] = s
		i += 1
	else:
		print(*r[::-1])


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
if sum(l) < n:
	print(-1)
	exit(0)
for i in range(m):
	if n - l[i] < i:
		print(-1)
		exit(0)
p = [0] * m
fr = n
for i in range(m - 1, -1, -1):
	p[i] = max(fr - l[i], i) + 1
	fr = p[i] - 1
print(*p)


(N, M) = list(map(int, input().split()))
L = list(map(int, input().split()))
if sum(L) < N:
	print(-1)
elif any([l + i > N for (i, l) in enumerate(L)]):
	print(-1)
else:
	S = [L[-1]]
	for i in list(reversed(L))[1:]:
		S.append(S[-1] + i)
	S = list(reversed(S))
	res = []
	for (num, (s, l)) in enumerate(zip(S, L)):
		if N - num >= s:
			for ss in S[num:]:
				res.append(N - ss + 1)
			break
		else:
			res.append(num + 1)
	print(' '.join(map(str, res)))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
sum_l = sum(l)
if sum_l < n:
	print(-1)
	exit()
diff = sum_l - n
prev = 1
ans = [0]
for i in range(m):
	ans.append(max(prev + ans[-1] - diff, ans[-1] + 1))
	diff -= prev - (ans[-1] - ans[-2])
	prev = l[i]
ans = ans[1:]
for i in range(m):
	if ans[i] + l[i] - 1 > n:
		print(-1)
		exit()
if ans[-1] + l[i] - 1 == n:
	print(*ans)
else:
	print(-1)


import sys
(n, m) = map(int, input().split())
l = list(map(int, input().split()))[::-1]
ans = [1]
rest = n - l[0] - m + 1
if rest < 0:
	print(-1)
	sys.exit()
border = l[0]
for i in range(1, m):
	m = min(rest, l[i] - 1)
	rest -= m
	ans.append(border + m - l[i] + 2)
	if ans[-1] < 1:
		print(-1)
		sys.exit()
	border += m + 1
if rest > 0:
	print(-1)
	sys.exit()
else:
	ans.reverse()
	print(*ans)


def main():
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	ind = int()
	for i in range(m):
		if n - l[i] < i:
			ind = 1
			break
	if ind or sum(l) < n:
		print(-1)
	else:
		over = sum(l) - n
		counter = int()
		while over > 0:
			if counter < m:
				k = l[counter] - 1
				l[counter] -= min(over, l[counter] - 1)
				over -= min(over, k)
				counter += 1
		place = [1]
		inc = 1 + l[0]
		for i in range(1, m):
			place.append(inc)
			inc += l[i]
		print(' '.join(map(str, place)))
main()


import sys
input = sys.stdin.readline
(n, m) = [int(a) for a in input().split()]
ls = [int(a) for a in input().split()]
fail = False
for i in range(m):
	if ls[i] > n - i:
		fail = True
		break
if fail:
	print(-1)
else:
	for i in range(1, m):
		ls[m - i - 1] += ls[m - i]
	if ls[0] < n:
		print(-1)
	else:
		remain = n
		s = [' '] * n
		for i in range(m):
			remain = min(remain, ls[i])
			s[i] = str(n - remain + 1)
			remain -= 1
		print(' '.join(s))


(N, M) = map(int, input().split())
L = [int(a) for a in input().split()]
m = (1 << 17) - 1
if sum(L) < N:
	print(-1)
else:
	s = N + 1
	ANS = [-1] * M
	for (i, l) in enumerate(L[::-1]):
		s = max(s - l, M - i)
		ANS[i] = s
		if s + l - 1 > N:
			print(-1)
			break
	else:
		print(*ANS[::-1])


(n, m) = map(int, input().split())
arr = [int(x) for x in input().split()]
if sum(arr) < n:
	print(-1)
	exit(0)
if m > n:
	print(-1)
	exit(0)
for i in range(m):
	if n - arr[i] < i:
		print(-1)
		exit(0)
ans = [0] * m
total = n
for i in range(m - 1, -1, -1):
	ans[i] = max(total - arr[i], i) + 1
	total = ans[i] - 1
print(*ans)


(n, m) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
ok = True
for i in range(m):
	if n - a[i] < i:
		ok = False
s = [0] * (m + 1)
for i in range(m - 1, -1, -1):
	s[i] = s[i + 1] + a[i]
if s[0] < n:
	ok = False
ans = []
left = 1
for i in range(m):
	ans.append(left)
	nxt = max(left + 1, n - s[i + 1] + 1)
	if nxt > left + a[i]:
		ok = False
		break
	left = nxt
if ok:
	print(' '.join(map(str, ans)))
else:
	print(-1)


from sys import stdin, stdout

def cout(x):
	print(x, end=' ')
	return
(n, m) = map(int, input().split())
v = [int(i) for i in stdin.readline().split()]
imp = [0 for i in range(m)]
imp.append(n)
jala = True
suma = 0
for i in reversed(range(m)):
	suma += v[i]
	imp[i] = max(i, imp[i + 1] - v[i])
	if imp[i] + v[i] > n:
		jala = False
if imp[0] > 0 or suma < n:
	jala = False
if jala:
	s = ''
	imp.pop()
	for x in imp:
		s += str(x + 1) + ' '
	print(s)
else:
	print(-1)


import sys
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
if sum(l) < n:
	print(-1)
	sys.exit(0)
pre = [1] * (m + 1)
max = m + l[-1] - 1
if max > n:
	print(-1)
	sys.exit(0)
flag = False
for i in range(m):
	if i + l[i] > n:
		flag = True
		break
if flag:
	print(-1)
	sys.exit(0)
for i in range(m - 2, -1, -1):
	if l[i] > 1:
		if l[i] - 1 + max <= n:
			max = max + l[i] - 1
			pre[i + 1] += l[i] - 1
		else:
			pre[i + 1] += n - max
			max = n
	if max == n:
		break
previous = 0
for i in range(m):
	previous = previous + pre[i]
	if pre[i] == 0:
		previous += 1
	print(previous, end=' ')
print()


import sys
import math
input = sys.stdin.readline
from functools import cmp_to_key

def pi():
	return int(input())

def pl():
	return int(input(), 16)

def ti():
	return list(map(int, input().split()))

def ts():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
mod = 1000000007
f = []

def fact(n, m):
	global f
	f = [1 for i in range(n + 1)]
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % m

def fast_mod_exp(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b = b >> 1
	return res

def inverseMod(n, m):
	return fast_mod_exp(n, m - 2, m)

def ncr(n, r, m):
	if r == 0:
		return 1
	return f[n] * inverseMod(f[n - r], m) % m * inverseMod(f[r], m) % m

def main():
	A()

def xdfs(root, v, sub, parent):
	st = [root]
	while len(st) > 0:
		node = st.pop()
		for i in range(len(v[node])):
			if v[node][i] != node:
				st.append(v[node][i])

def X():
	try:
		t = pi()
		while t:
			t -= 1
			n = pi()
			v = [[] for i in range(n)]
			for i in range(n - 1):
				[x, y] = ti()
				v[x - 1].append(y - 1)
				v[y - 1].append(x - 1)
			m = pi()
			p = ti()
			e = [0 for i in range(n - 1)]
			sub = [0 for i in range(n)]
			dfs(0, v, sub, -1)
			for i in range(1, n):
				e[i - 1] = sub[i] * (n - sub[i])
			if len(p) < n - 1:
				while len(p) < n - 1:
					p.append(1)
			p = sorted(p)
			if len(p) > n - 1:
				x = 1
				for i in range(n - 2, len(p)):
					x = x * p[i]
				while len(p) > n - 2:
					p.pop()
				p.append(x)
			e = sorted(e)
			res = 0
			for i in range(n - 1):
				res = (res + p[i] * e[i]) % mod
			print(res)
	except:
		print(sys.exc_info())

def bfs(v, root):
	q = [root, None]
	l = 0
	visited = [0 for i in range(len(v))]
	dist = [0 for i in range(len(v))]
	while len(q) > 0:
		node = q.pop(0)
		if node is not None:
			visited[node] = 1
			dist[node] = l
			for i in range(len(v[node])):
				if visited[v[node][i]] == 0:
					visited[v[node][i]] = 1
					q.append(v[node][i])
		else:
			l += 1
			if len(q) != 0:
				q.append(None)
	return dist

def B():
	n = pi()
	v = [[] for i in range(n)]
	for i in range(n - 1):
		[x, y] = ti()
		v[x - 1].append(y - 1)
		v[y - 1].append(x - 1)
	leafs = []
	for i in range(n):
		if len(v[i]) == 1:
			leafs.append(i)
	mn = 1
	d = bfs(v, leafs[0])
	for i in range(1, len(leafs)):
		if d[leafs[i]] % 2 != 0:
			mn = 3
			break
	count = 0
	for i in range(n):
		f = 0
		for j in range(len(v[i])):
			if len(v[v[i][j]]) == 1:
				f = 1
				break
		if f:
			count += 1
	mx = n - 1 - len(leafs) + count
	print(mn, mx)

def A():
	[n, m] = ti()
	l = ti()
	res = []
	s = 0
	for i in range(m):
		s += l[i]
	pre = [0 for i in range(m)]
	for i in range(m):
		if i != 0:
			pre[i] = pre[i - 1] + l[i]
		else:
			pre[i] = l[i]
	if s == n:
		for i in range(m):
			if i == 0:
				res.append(i + 1)
			else:
				res.append(pre[i - 1] + 1)
		print(*res, sep=' ')
		return
	if s < n:
		print(-1)
		return
	if s > n:
		d = s - n
		for i in range(m):
			if n - l[i] < i:
				print(-1)
				return
			if i != m - 1:
				res.append(i + 1)
			else:
				res.append(n - l[i] + 1)
		print(*res, sep=' ')
main()


from sys import stdin, stdout
(n, m) = [int(x) for x in stdin.readline().split()]
ops = [int(x) for x in stdin.readline().split()]
s = sum(ops)
if s < n:
	print(-1)
else:
	diff = s - n
	cur = 0
	out = []
	valid = True
	for x in ops:
		if cur + x > n:
			valid = False
			break
		out.append(str(cur + 1))
		ad = max(1, x - diff)
		diff -= x - ad
		cur += ad
	if valid:
		print(' '.join(out))
	else:
		print(-1)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
mod = 1000000007

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def lcm(a, b):
	return abs(a // gcd(a, b) * b)

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def arr1d(n, v):
	return [v] * n

def arr2d(n, m, v):
	return [[v] * m for _ in range(n)]

def arr3d(n, m, p, v):
	return [[[v] * p for _ in range(m)] for i in range(n)]

def solve():
	(n, m) = sep()
	l = lis()
	total = sum(l)
	if total < n:
		print(-1)
		return
	rem = total - n
	pos = 1
	ans = []
	for (i, x) in enumerate(l):
		ans += [pos]
		if pos + x > n + 1:
			print(-1)
			return
		saved = min(rem, x - 1)
		rem -= saved
		pos += x - saved
	print(*ans)
solve()


def main():
	import sys
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	L = list(map(int, input().split()))
	if sum(L) < N:
		print(-1)
		exit()
	ans = [0] * M
	left = N
	for i in range(M - 1, -1, -1):
		if left - L[i] >= i:
			ans[i] = left - L[i] + 1
			left -= L[i]
		else:
			if i + L[i] - 1 >= N:
				print(-1)
				exit()
			ans[i] = i + 1
			left = i
	print(*ans)
main()


(n, m) = map(int, input().split())
l = [int(x) for x in input().split()]
(s, res, p) = ([], [], 0)
s.append(l[-1])
for i in range(m - 2, -1, -1):
	s.append(s[m - i - 2] + l[i])
s.reverse()
if s[0] < n:
	print(-1)
else:
	for i in range(m):
		p = max(n - s[i] + 1, p + 1)
		if not 1 <= p <= n - l[i] + 1:
			p = 0
			break
		else:
			res.append(p)
	if p + l[-1] == n + 1:
		print(*res)
	else:
		print(-1)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
ls = sum(l)
ans = []
import sys
if ls < n or m - 1 + l[-1] > n:
	print(-1)
	sys.exit()
cut = []
remain = ls - n
for i in range(m):
	if l[i] - 1 < remain:
		cut.append(l[i] - 1)
		remain -= l[i] - 1
	else:
		cut.append(remain)
		remain = 0
l2 = [0] * m
for i in range(m):
	l2[i] = l[i] - cut[i]
now = 1
for i in range(m):
	ans.append(now)
	now += l2[i]
for i in range(m):
	if l[i] + ans[i] - 1 > n:
		print(-1)
		sys.exit()
print(*ans)


(n, m) = map(int, input().split())
blocks = [int(x) for x in input().split()]
b2 = [(blocks[i], i) for i in range(len(blocks))]
s = sum(blocks)
if s < n:
	print(-1)
else:
	p = [0] * len(b2)
	rem = s
	x = n
	i = 0
	br = 1
	f = 0
	while rem > x and i != n:
		if b2[i][0] + i > n:
			br = 0
			break
		rem -= b2[i][0]
		p[b2[i][1]] = i + 1
		x -= 1
		i += 1
	while rem > 0 and br:
		f = 1
		p[b2[i][1]] = n - rem + 1
		rem -= b2[i][0]
		i += 1
	if f:
		print(*p)
	else:
		print(-1)


(n, m) = map(int, input().split())
new = list(map(int, input().split()))
a = []
if sum(new) < n:
	print(-1)
	exit()
for i in range(m):
	if new[i] + i > n:
		print(-1)
		exit()
for i in range(m):
	a.append((new[i], i))
suff = [-1] * m
suff[-1] = a[-1][0]
for i in range(m - 2, -1, -1):
	suff[i] = suff[i + 1] + a[i][0]
ans = [i for i in range(1, m + 1)]
for i in range(m):
	ans[i] = max(ans[i], n - suff[i] + 1)
print(*ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
s = sum(a)
if s < n:
	print(-1)
else:
	r = []
	diff = s - n
	curr = 0
	valid = True
	for i in range(m):
		r.append(curr + 1)
		curr += a[i]
		if curr > n:
			valid = False
		d = min(diff, a[i] - 1)
		curr -= d
		diff -= d
	if valid:
		print(*r)
	else:
		print(-1)


from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
(n, m) = mi()
a = li()
if m > n:
	print('-1')
	exit()
if sum(a) < n:
	print('-1')
	exit()
for i in range(m):
	if a[i] > n - i:
		print('-1')
		exit()
p = [0] * (m + 1)
p[m] = n
q = [0] * (m + 1)
for i in range(m - 1, -1, -1):
	p[i] = max(i, p[i + 1] - a[i])
	q[i] = p[i] + 1
q = q[:m]
print(*q)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
possible = 1
t = 0
for i in range(m):
	if l[i] + i > n:
		possible = 0
	t += l[i]
if t < n:
	possible = 0
if possible == 0:
	print(-1)
else:
	d = t - n
	s = [0] * m
	s[0] = 1
	for i in range(m - 1):
		if d == 0:
			s[i + 1] = s[i] + l[i]
		elif d >= l[i]:
			d -= l[i]
			d += 1
			s[i + 1] = s[i] + 1
		else:
			s[i + 1] = s[i] + l[i] - d
			d = 0
	print(*s)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
s = sum(a)
if s < n:
	print(-1)
else:
	r = []
	diff = s - n
	curr = 0
	valid = True
	for i in range(m):
		r.append(curr + 1)
		curr += a[i]
		if curr > n:
			valid = False
		d = min(diff, a[i] - 1)
		curr -= d
		diff -= d
	if valid:
		print(*r)
	else:
		print(-1)


R = lambda : map(int, input().split())
(n, m) = R()
a = list(R())

def solve(a, n, m):
	if m > n:
		print(-1)
	b = [0] * m
	t = 0
	for i in range(m - 1, -1, -1):
		t += a[i]
		b[i] = t
	b.append(0)
	ar = []
	cur = 0
	for i in range(m):
		if b[i] < n - cur:
			print(-1)
			return
		if a[i] > n - cur:
			print(-1)
			return
		ar.append(cur)
		cur += 1
		while b[i + 1] < n - cur:
			cur += 1
	print(*[x + 1 for x in ar])
	return
solve(a, n, m)


(n, m) = map(int, input().split())
l = [0] + list(map(int, input().split()))
for i in range(1, m + 1):
	if l[i] + i - 1 > n:
		print(-1)
		exit()
suffix_sum = [0] * (m + 2)
for i in range(m + 1)[::-1]:
	suffix_sum[i] = suffix_sum[i + 1] + l[i]
if suffix_sum[1] < n:
	print(-1)
	exit()
p = [0] * (m + 1)
for i in range(1, m + 1):
	p[i] = max(i, n - suffix_sum[i] + 1)
print(*p[1:])


import sys
(n, m) = map(int, input().split(' '))
ms = list(map(int, input().split(' ')))
total = sum(ms)
if total < n:
	print(-1)
	sys.exit(0)
start = 1
s = [i for i in range(1, m + 1)]
mi = m - 1
needr = n
shift = 0
while mi >= 0:
	s[mi] -= shift
	if s[mi] + ms[mi] - 1 > n or s[mi] <= 0:
		print(-1)
		sys.exit(0)
	if s[mi] + ms[mi] - 1 < needr:
		sh = needr - (s[mi] + ms[mi] - 1)
		s[mi] += sh
	needr = min(needr, s[mi] - 1)
	mi -= 1
print(' '.join((str(x) for x in s)))


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

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

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return [int(x) for x in input().split()]

def sapin():
	return [int(x) for x in input()]
t = 1
for _ in range(t):
	(n, m) = mapin()
	l = [int(x) for x in input().split()]
	fl = 1
	for i in range(m):
		if l[i] + i > n:
			fl = 0
			print(-1)
			break
	if fl:
		s = [0] * (m + 1)
		for i in range(m - 1, -1, -1):
			s[i] = s[i + 1] + l[i]
		if s[0] < n:
			fl = 0
			print(-1)
			break
		if fl:
			fi = []
			for i in range(m):
				fi.append(max(i + 1, n - s[i] + 1))
			print(*fi)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
if sum(A) < n:
	print(-1)
else:
	ANS = [i for i in range(m)]
	MCOLORED = 0
	for i in range(m):
		if i + A[i] > n:
			print(-1)
			sys.exit()
		MCOLORED = max(MCOLORED, i + A[i])
	MNC = n - 1
	ind = m - 1
	while ANS[ind] + A[ind] - 1 < MNC:
		x = MNC - A[ind] + 1
		if ind != 0 and ANS[ind - 1] >= x:
			print(-1)
			sys.exit()
		ANS[ind] = x
		MNC = x - 1
		ind -= 1
	ANS2 = [a + 1 for a in ANS]
	print(*ANS2)


(n, m) = map(int, input().split())
l = [0] + list(map(int, input().split()))
suff = [0] * (m + 1)
suff[m] = m - 1 + l[m]
for i in range(m - 1, 0, -1):
	suff[i] = max(suff[i + 1], i - 1 + l[i])
sol = [0] * (n + 1)
(ok, now) = (1, 1)
for i in range(1, m + 1):
	k = suff[i] - (i - 1)
	if k > n - now + 1:
		ok = 0
		break
	if i == m:
		cat = l[i]
	else:
		cat = min(l[i], n - now + 1 - (suff[i + 1] - i))
	sol[i] = now
	now += cat
ok &= now == n + 1
if ok:
	for i in range(1, m + 1):
		print(sol[i], end=' ')
else:
	print(-1)


import sys
input = sys.stdin.readline
from sys import stdin, stdout

def main():
	(n, m) = [int(s) for s in input().split()]
	l = [int(s) for s in input().split()]
	sums = [0] * m
	sums[0] = l[0]
	for i in range(1, m):
		sums[i] = sums[i - 1] + l[i]
	ww = 0
	for i in range(m):
		ww = max(ww, i + l[i])
	if max(ww, m + l[-1] - 1) > n:
		print(-1)
	elif sums[-1] < n:
		print(-1)
	elif m == 1:
		print(1)
	else:
		ans = [0] * m
		w = m + l[-1] - 1
		ans[-1] = n - l[-1] + 1
		j = m - 2
		while w + l[j] - 1 < n:
			w += l[j] - 1
			ans[j] = ans[j + 1] - l[j]
			j -= 1
		if j >= 0:
			for i in range(j + 1):
				ans[i] = i + 1
		print(*ans)
main()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
out = []
curr = 0
lastPoss = [n - l[i] for i in range(m)]
for i in range(m - 2, -1, -1):
	lastPoss[i] = min(lastPoss[i], lastPoss[i + 1] - 1)
if lastPoss[0] < 0:
	print(-1)
else:
	for i in range(m):
		v = l[i]
		out.append(min(curr, lastPoss[i]))
		curr += v
	if curr >= n:
		print(' '.join(map(lambda x: str(x + 1), out)))
	else:
		print(-1)


line = input().split()
n = int(line[0])
m = int(line[1])
line = [int(x) for x in input().split()]
impossible = False
total_spaces = 0
for i in range(m):
	curr = line[i]
	if n - curr < i:
		impossible = True
		break
	total_spaces += curr
if impossible or total_spaces < n:
	print(-1)
else:
	index = 0
	remaining_slots_to_retrocede = total_spaces - n
	ans = []
	for i in range(m):
		ans.append(index)
		index += line[i]
		max_sots_to_retrocede = line[i] - 1
		index -= min(max_sots_to_retrocede, remaining_slots_to_retrocede)
		remaining_slots_to_retrocede -= min(max_sots_to_retrocede, remaining_slots_to_retrocede)
	for starting_point in ans:
		print(starting_point + 1, end=' ')
	print()


temp = input().split()
n = int(temp[0])
m = int(temp[1])
l = input().split()
for i in range(m):
	l[i] = int(l[i])
valid = True
total = 0
for i in range(m):
	if l[i] + i > n:
		valid = False
	total += l[i]
if total < n:
	valid = False
if valid:
	done = [x + 1 for x in range(m)]
	final = m - 1
	unfilled = n
	last = m - 1 + l[m - 1]
	while last < unfilled:
		done[final] = unfilled - l[final] + 1
		unfilled = unfilled - l[final]
		final -= 1
		last = final + l[final]
	print(done[0], end='')
	for i in range(1, len(done)):
		print(' ' + str(done[i]), end='')
else:
	print(-1)


import os
import sys
from io import BytesIO, IOBase
import threading
from collections import Counter

def main():
	for _ in range(1):
		(n, m) = map(int, input().split())
		arr = list(map(int, input().split()))
		sm = sum(arr)
		ans = [0] * m
		st = n
		colored = n + 1
		for i in range(m):
			ans[i] = min(n - arr[i] + 1, st - arr[i] + 1)
			st -= 1
		pt = 1
		for i in ans:
			if i < 1:
				print(-1)
				return
		for i in range(m - 1, -1, -1):
			if ans[i] <= pt:
				print(*ans)
				return ()
			else:
				ans[i] = pt
				pt = ans[i] + arr[i]
		print(-1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(N, M) = input().split(' ')
(N, M) = (int(N), int(M))
L = input().split(' ')
L = list((int(x) for x in L))

def answer(N, M, L):
	offsets = [0]
	for i in range(M - 1):
		offsets += [1]
	overhang = 0
	for ii in range(M - 1):
		i = M - 1 - ii
		left_edge = i + 1
		right_edge = left_edge + L[i] - 1 + overhang
		if right_edge > N:
			return '-1'
		max_right_edge = right_edge + L[i - 1] - 1
		if max_right_edge > N:
			max_right_edge = N
		offsets[i] += max_right_edge - right_edge
		parent_right_edge = i + L[i - 1] - 1
		overhang = max(0, max_right_edge - parent_right_edge)
	if L[0] + overhang < N:
		return '-1'
	pos = 1
	ret = [1]
	for o in offsets[1:]:
		pos += o
		ret += [pos]
	return ' '.join((str(r) for r in ret))
print(answer(N, M, L))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
total = sum(l)
if total < n:
	print(-1)
	exit()
rem = total - n
pos = 1
ans = []
for (i, x) in enumerate(l):
	ans += [pos]
	if pos + x > n + 1:
		print(-1)
		exit()
	saved = min(rem, x - 1)
	rem -= saved
	pos += x - saved
print(*ans)


import sys
import itertools
input = sys.stdin.readline

def main():
	(N, M) = [int(x) for x in input().split()]
	L = [int(x) for x in input().split()]
	if sum(L) < N:
		print(-1)
		return
	ruiseki = list(itertools.accumulate(L[::-1]))
	ans = []
	for (i, l) in enumerate(L):
		if i == 0:
			ans.append(1)
			continue
		elif i == M - 1:
			x = N - ruiseki[-i - 1] + 1
			ans.append(x)
			if ans[i] - ans[i - 1] > L[i - 1]:
				print(-1)
				return
			if ans[i] <= ans[i - 1]:
				print(-1)
				return
		else:
			x = N - ruiseki[-i - 1] + 1
			x = max(ans[i - 1] + 1, x)
			ans.append(x)
			if N + 1 - x < l:
				print(-1)
				return
			if ans[i] - ans[i - 1] > L[i - 1]:
				print(-1)
				return
	print(*ans)
main()