最近Evlampy安装了一款有趣的电脑游戏,其中一个方面是将军队分成几个小组,然后与敌人的小组作战。让我们考虑一下战斗的简化版本。
在最近的战斗中,Evlampy 应该与一支由 $$$m$$$ 团体组成的敌军作战,其中第 $$$i$$$ 拥有 $$$hp_i$$$ 生命值。
Evlampy 的军队由 $$$n$$$ 平等的士兵组成。在每次战斗之前,他应该将他的军队精确地分成 $$$m$$$ 个小组(可能是空的),以便小组的总规模为 $$$n$$$。战斗是一步步进行的。 Evlampy 的每一步都会攻击一组敌人。因此,每个步骤都用 $$$m$$$ 整数数组 $$$a_1, a_2, \ldots, a_m$$$ 来描述,这意味着第 $$$i$$$ 个 Evlampy 小组攻击第 $$$a_i$$$ 个敌方小组。不同的群体可以攻击同一群体,每一步都会独立选择数组$$$a$$$。
每一步之后,每个敌方队伍的生命值都会减少,数量等于在这一步攻击该敌方队伍的 Evlampy 队伍中的士兵总数。一旦敌方生命值为零或负数,就会被消灭。 Evlampy 的士兵不会失去生命值。
步骤示例。绿色圆圈中的数字代表Evlampy队伍中的士兵数量,箭头代表攻击,红色圆圈中的数字代表敌方队伍的生命值,蓝色数字代表该步骤后生命值将减少多少。
Evlampy知道即将到来的战斗将需要整个晚上。他很伤心,因为这样他就没有足够的时间完成作业。现在,Evlampy 希望您编写一个程序,帮助他以尽可能少的步数获胜。你能帮助他吗?
换句话说,找到消灭所有敌人群体所需的最少步骤,并展示一种可能的方法。找到将军队分成 $$$m$$$ 组的要求以及每个步骤的数组 $$$a$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 10^{6}$$$) — Evlampy 军队中的士兵数量和敌军中的团体数量。 $$$m$$$ 也等于 Evlampy 可以将军队分成的最大可能数量。
第二行包含 $$$m$$$ 整数 $$$hp_1, hp_2, \ldots, hp_m$$$ ($$$1 \leq hp_i \leq 10^{6}$$$) — 每个敌人群体的生命值。
保证$$$hp_i$$$的总和不超过$$$10^{6}$$$。
输出
打印一个整数 $$$t$$$ — 赢得战斗所需的最小可能步数。
之后打印 $$$m$$$ 整数 $$$s_1, s_2, \ldots, s_m$$$ ($$$s_i \ge 0$$$, $$$s_1 + s_2 + \ldots + s_m = n$$$),这意味着 Evlampy 军队的第 $$$i$$$ 组应该包含$$$s_i$$$ 士兵。
在接下来的 $$$t$$$ 行中打印 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_i \le m$$$) - 一个步骤的描述。整数意味着在相应的步骤中,第 $$$i$$$ 个 Evlampy 小组应该攻击第 $$$a_i$$$ 个敌方小组。它可以攻击已经被摧毁的群体。
示例
输入 #1
13 7 6 4 3 7 2 1 5
输出 #1
3 0 1 2 3 1 2 4 2 6 2 4 4 2 4 3 1 7 1 7 7 1 3 1 5 3 7 5 1
输入 #2
6 5 3 3 3 3 3
输出 #2
3 3 3 0 0 0 1 2 3 4 5 3 4 5 5 5 5 5 5 5 5
输入 #3
7 4 1 5 9 2
输出 #3
3 1 2 4 0 1 4 2 3 2 3 3 3 3 3 3 3
注意
第一个示例如下所示。