CF1329A Dreamoon Likes Coloring

Dreamoon 非常喜欢给格子上色。 有一排 $n$ 个格子，初始时所有格子都是空的（没有任何颜色）。格子的编号从 $1$ 到 $n$。 你会得到一个整数 $m$ 和 $m$ 个整数 $l_1, l_2, \ldots, l_m$（$1 \le l_i \le n$）。 Dreamoon 将进行 $m$ 次操作。 在第 $i$ 次操作中，Dreamoon 会从区间 $[1, n-l_i+1]$（包含端点）中选择一个数 $p_i$，然后将从 $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$ 次操作后，每种颜色至少出现一次，且所有格子都被上色。 如果有多组可行解，你可以输出任意一组。

由 ChatGPT 4.1 翻译