题目描述

在一场音乐会上，一支有 $n$ 名乐师的乐队共连续演奏 $t$ 分钟，但每名乐师都有自己想要休息的时长。对于第 $i$ 名乐师，他想休息 $a_i$ 分钟。但为了整体的和谐，不能有三个及以上的乐师在同一个时刻休息（但是可以在上一个乐师刚刚结束的时刻开始下一个人的休息）。

请你安排每名乐师开始休息的时刻。

输入格式

输入第一行为两个整数 $t,n$。

第二行为 $n$ 个整数 $a_1,\dots ,a_n$，表示每名乐师希望休息的时长。

输出格式

输出一行 $n$ 个整数，表示安排每名乐师的开始休息的时刻，按照输入的顺序输出每名乐师。

注意：尽管方案可能不唯一，但数据保证方案一定存在，本题使用SPJ。

8 3
4 4 4

0 2 4

10 5
7 5 1 2 3

3 3 9 0 0

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le t\le 5000$，$1\le n\le 500$。

说明

题目译自 COCI2007-2008 CONTEST #4 T4 MUZICARI。