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