{"problem":{"name":"D. Polycarp's Picture Gallery","description":{"content":"Polycarp loves not only to take pictures, but also to show his photos to friends. On his personal website he has recently installed a widget that can display _n_ photos with the scroll option. At each","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF81D"},"statements":[{"statement_type":"Markdown","content":"Polycarp loves not only to take pictures, but also to show his photos to friends. On his personal website he has recently installed a widget that can display _n_ photos with the scroll option. At each moment of time the widget displays exactly one photograph with the option showing the previous/next one. From the first photo, you can switch to the second one or to the _n_\\-th one, from the second photo you can switch to the third one or to the first one, etc. Thus, navigation is performed in a cycle.\n\nPolycarp's collection consists of _m_ photo albums, the _i_\\-th album contains _a__i_ photos. Polycarp wants to choose _n_ photos and put them on a new widget. To make watching the photos interesting to the visitors, he is going to post pictures so that no two photos from one album were neighboring (each photo will have exactly two neighbors, the first photo's neighbors are the second and the _n_\\-th one).\n\nHelp Polycarp compile a photo gallery. Select _n_ photos from his collection and put them in such order that no two photos from one album went one after the other.\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (3 ≤ _n_ ≤ 1000, 1 ≤ _m_ ≤ 40), where _n_ is the number of photos on the widget, and _m_ is the number of albums. The second line contains _m_ integers _a_1, _a_2, ..., _a__m_ (1 ≤ _a__i_ ≤ 1000), where _a__i_ is the number of photos in the _i_\\-th album.\n\n## Output\n\nPrint the single number _\\-1_ if there is no solution. Otherwise, print _n_ numbers _t_1, _t_2, ..., _t__n_, where _t__i_ represents the number of the album of the _i_\\-th picture in the widget. The albums are numbered from 1 in the order of their appearance in the input. If there are several solutions, print any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Polycarp 不仅喜欢拍照，还喜欢向朋友展示他的照片。他最近在他的个人网站上安装了一个小部件，可以显示 #cf_span[n] 张照片，并支持滚动功能。在任意时刻，该小部件仅显示一张照片，并提供查看上一张或下一张照片的选项。从第一张照片可以切换到第二张或第 #cf_span[n] 张照片，从第二张照片可以切换到第三张或第一张照片，依此类推。因此，导航是以循环方式进行的。\n\nPolycarp 的收藏包含 #cf_span[m] 个相册，第 #cf_span[i] 个相册包含 #cf_span[ai] 张照片。Polycarp 希望从中选出 #cf_span[n] 张照片，并将它们放置在一个新的小部件上。为了使访客观看照片变得有趣，他打算按如下方式排列照片：同一个相册的任意两张照片不能相邻（每张照片恰好有两个邻居，第一张照片的邻居是第二张和第 #cf_span[n] 张照片）。\n\n请帮助 Polycarp 组建一个照片画廊：从他的收藏中选出 #cf_span[n] 张照片，并将它们排列成一个序列，使得没有两张来自同一相册的照片相邻。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[3 ≤ n ≤ 1000]，#cf_span[1 ≤ m ≤ 40]），其中 #cf_span[n] 是小部件上的照片数量，#cf_span[m] 是相册数量。第二行包含 #cf_span[m] 个整数 #cf_span[a1, a2, ..., am]（#cf_span[1 ≤ ai ≤ 1000]），其中 #cf_span[ai] 表示第 #cf_span[i] 个相册中的照片数量。\n\n如果无解，请输出 _-1_；否则，请输出 #cf_span[n] 个数字 #cf_span[t1, t2, ..., tn]，其中 #cf_span[ti] 表示小部件中第 #cf_span[i] 张照片所属的相册编号。相册按输入顺序从 1 开始编号。如果存在多个解，输出任意一个即可。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[3 ≤ n ≤ 1000]，#cf_span[1 ≤ m ≤ 40]），其中 #cf_span[n] 是小部件上的照片数量，#cf_span[m] 是相册数量。第二行包含 #cf_span[m] 个整数 #cf_span[a1, a2, ..., am]（#cf_span[1 ≤ ai ≤ 1000]），其中 #cf_span[ai] 表示第 #cf_span[i] 个相册中的照片数量。\n\n## Output\n\n如果无解，请输出 _-1_；否则，请输出 #cf_span[n] 个数字 #cf_span[t1, t2, ..., tn]，其中 #cf_span[ti] 表示小部件中第 #cf_span[i] 张照片所属的相册编号。相册按输入顺序从 1 开始编号。如果存在多个解，输出任意一个即可。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of photos to be arranged.  \nLet $ m \\in \\mathbb{Z} $ be the number of albums.  \nLet $ \\mathbf{a} = (a_1, a_2, \\dots, a_m) \\in \\mathbb{Z}_{>0}^m $, where $ a_i $ is the number of available photos in album $ i $.  \n\nLet $ \\mathbf{t} = (t_1, t_2, \\dots, t_n) \\in \\{1, 2, \\dots, m\\}^n $ be the sequence of album indices assigned to the $ n $ positions in the circular widget.\n\n**Constraints**  \n1. $ \\sum_{i=1}^m a_i \\geq n $  \n2. For each $ j \\in \\{1, \\dots, n\\} $, the album index $ t_j $ must satisfy:  \n   $$\n   \\left| \\{ k \\in \\{1, \\dots, n\\} \\mid t_k = i \\} \\right| \\leq a_i \\quad \\text{for all } i \\in \\{1, \\dots, m\\}\n   $$\n3. **No two adjacent photos (including wraparound) are from the same album**:  \n   $$\n   t_j \\neq t_{j+1} \\quad \\text{for all } j \\in \\{1, \\dots, n-1\\}, \\quad \\text{and} \\quad t_n \\neq t_1\n   $$\n\n**Objective**  \nFind any sequence $ \\mathbf{t} \\in \\{1, \\dots, m\\}^n $ satisfying the above constraints.  \nIf no such sequence exists, output $-1$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF81D","tags":["constructive algorithms","greedy"],"sample_group":[["4 3\n1 3 5","3 1 3 2"],["10 2\n5 5","2 1 2 1 2 1 2 1 2 1"],["10 3\n1 10 3","\\-1"]],"created_at":"2026-03-03 11:00:39"}}