Dreamoon Likes Coloring
Contest: Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov!
Difficulty rating: 1800
Tags: constructive algorithms, greedy, implementation, math

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 3
3 2 2

Example output:
2 4 1

Example input:
10 1
1

Example output:
-1

Editorial:
After reading the statement, you may find this is a problem that will be tagged as "constructive algorithms" in Codefores. And you also can find this problem is just problem A in Div. 1. So basically we can expect there exist some simple methods to solve it.
If a "constructive algorithms" problem asks you to determine whether the solution exists or not, usually they have a common pattern(especially in problem hardness which is before Div. 1 B(inclusive)), this is, there are some simple constraints can divide test data into "Yes", and "No". Therefore, the first thing to solve this problem is finding some trivial conditions that cannot achieve Dreamoon's hope.
After some try, you may find there are two trivial conditions that achieving Dreamoon's hope is impossible. The two conditions are listed as follows:
1. Sum of $$$l_i$$$ is less than $$$n$$$. In this condition, there always is at least one empty grid.
2. There exists some $$$i$$$ such that $$$l_i + i - 1 > n$$$. If $$$n - l_i < i - 1$$$, it means after you do $$$i$$$-th operation, there only $$$n - l_i$$$ grid is not colored by $$$i$$$-th color. So at least one of previous $$$i-1$$$ color will disapear after this operation.
Now I want to talk about another feature of some "constructive algorithms" first.
Sometimes, the condition given by the problem is to "open", this is to say that if we added some more strict constraint, the problem is still can be solved. And when the constraint it more strict, we can deduce the solution more easily.
One of common "strict constraint" is "sorted". I believe you have ever seen many problems that the first step is sorting something. Now, we also want to apply "sorted" in the problem.
After applying "sort", we firstly consider the edge cases of above two impossible conditions. The first case is "sum of $$$l_i$$$ is equal to $$$n$$$". In this case, we have a unique solution after applying "sort", $$$p_i = m - \sum\limits_{j=i+1}^{m} l_j + 1$$$. The second case is $$$l_i + i - 1 = n$$$ is hold for all $$$i$$$. In this case, there is also a unique solution that $$$p_i = i$$$. The two cases coressond to $$$n$$$ is largest and $$$n$$$ is smallest among all $$$n$$$ that exist solutions for same $$$l_i$$$. And for same $$$l_i$$$, when we decrase $$$n$$$ from the largest possible value, we can just change $$$p_i$$$ from $$$m - \sum\limits_{j=i+1}^{m} l_j + 1$$$ to $$$i$$$ for some smallest indices $$$i$$$ to get solution. To sum it up, finally, we get the answer. The answer is just $$$p_i = \max(i, n - suffix\_sum[i] + 1)$$$, for each $$$i$$$.
There exist many other methods to construct solutions. I believe the construction method one can think out is relative to the study experience.