← 返回题目列表

Codeforces · 1329/A

A. Dreamoon 喜欢着色

中文机器翻译题面 查看原题

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$$$,并以第 $$$i$$$ 颜色绘制从 $$$p_i$$$ 到 $$$p_i+l_i-1$$$(含)的所有单元格。请注意,单元格可能会多次着色,在这种情况下,单元格将具有最新操作的颜色。

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$$$ 操作之后,所有颜色应该至少出现一次,并且所有单元格都应该着色。

如果有多种可能的解决方案,您可以打印任何一个。

示例

输入 #1

5 3
3 2 2

输出 #1

2 4 1

输入 #2

10 1
1

输出 #2

-1