A. Dreamoon любит красить
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Dreamoon очень любит красить клетки.

Есть ряд из $$$n$$$ клеток. Исходно, все клетки пустые (не содержат никакой цвет). Клетки пронумерованы от $$$1$$$ до $$$n$$$.

Вам дано целое число $$$m$$$ и $$$m$$$ целых чисел $$$l_1, l_2, \ldots, l_m$$$ ($$$1 \le l_i \le n$$$)

Dreamoon совершит $$$m$$$ операций.

В $$$i$$$-й операции, Dreamoon выберет число $$$p_i$$$ из отрезка $$$[1, n-l_i+1]$$$ (включительно) и покрасит все клетки от $$$p_i$$$ до $$$p_i+l_i-1$$$ (включительно) в $$$i$$$-й цвет. Обратите внимание, что клетки могут быть покрашены несколько раз, в таком случае, клетка будет покрашена в цвет из самой последней операции.

Dreamoon надеется, что после $$$m$$$ операций, все цвета будут встречаться хотя бы один раз и все клетки будут покрашены. Пожалуйста, помогите Dreamoon выбрать $$$p_i$$$ в каждой операции, чтобы удовлетворить всем ограничениям.

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

В первой строке записаны два целых числа $$$n,m$$$ ($$$1 \leq m \leq n \leq 100\,000$$$).

Во второй строке записано $$$m$$$ целых чисел $$$l_1, l_2, \ldots, l_m$$$ ($$$1 \leq l_i \leq n$$$).

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

Если невозможно совершить $$$m$$$ операций, чтобы удовлетворить всем ограничениям, выведите «-1» (без кавычек).

Иначе, выведите $$$m$$$ целых чисел $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \leq n - l_i + 1$$$), после этих $$$m$$$ операций, все цвета должны встречаться хотя бы один раз и все клетки должны быть покрашены.

Если есть несколько возможных решений, вы можете вывести любое.

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