← 返回题目列表

Codeforces · 81/D

D. 坡旅甲的画廊

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

Polycarp不仅喜欢拍照,还喜欢向朋友展示他的照片。在他的个人网站上,他最近安装了一个小部件,可以通过滚动选项显示 n 张照片。在每个时刻,小部件都会准确显示一张照片,并提供显示上一张/下一张照片的选项。从第一张照片可以切换到第二张或第n张,从第二张照片可以切换到第三张或第一张,以此类推,如此循环进行导航。

Polycarp的收藏由m张相册组成,第i张相册包含ai照片。 Polycarp 想要选择 n 张照片并将它们放在一个新的小部件上。为了使访问者观看照片变得有趣,他将发布照片,以便一个相册中没有两张照片是相邻的(每张照片将恰好有两个邻居,第一张照片的邻居是第二张和第 n 张照片)。

帮助 Polycarp 编译照片库。从他的收藏中选择n张照片,并将它们按这样的顺序排列,即一张相册中没有两张照片是一张接一张的。

输入

第一行包含两个整数 n 和 m (3 ≤ n ≤ 1000, 1 ≤ m ≤ 40),其中 n 是小部件上的照片数量,m 是相册数量。第二行包含 m 个整数 a1, a2, ..., am (1 ≤ ai ≤ 1000),其中 ai 是第 i 个相册中的照片数量。

输出

如果无解,则打印单个数字-1。否则,打印n个数字t1,t2,...,tn,其中ti表示小部件中第i张图片的相册编号。专辑按照它们在输入中出现的顺序从 1 开始编号。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

4 3
1 3 5

输出 #1

3 1 3 2

输入 #2

10 2
5 5

输出 #2

2 1 2 1 2 1 2 1 2 1

输入 #3

10 3
1 10 3

输出 #3

-1