著名的民间乐团“The Drinking Musicians”要来你们小镇了。这些音乐家不仅演奏技术高超，而且脾气暴躁。他们从不准时到达，不知道自己身处哪个城市，还经常找不到舞台。

此外，在音乐会期间，每位音乐家都会在某个时刻进行一次休息。如果同时有三名或更多的音乐家在休息，他们就会在镇上闹事，而乐团的其他人则会陷入恐慌并弹错和弦。

音乐会将持续 $T$ 分钟，在此期间，这 $N$ 名成员中的每一个人都会进行一次休息。每位成员的休息时长是已知的。

请通过编写一个程序来帮助音乐会的组织者，确定如何安排成员的休息时间，使得在任何给定的时刻，最多只有两名成员同时缺席。所有的休息必须完全在音乐会期间进行。

输入格式

第一行包含两个整数 $T$ 和 $N$（$1 \le T \le 5000$，$1 \le N \le 500$），分别表示音乐会的时长（分钟）和乐团中的音乐家数量。

第二行包含 $N$ 个由单个空格分隔的整数，表示每位成员的休息时长（分钟）。

注意：输入数据保证一定存在解（尽管解可能不唯一）。

输出格式

对于每个音乐家，输出一个整数，表示该音乐家在开始休息前在舞台上度过的时长（分钟）。

按照输入中给出音乐家的顺序输出。

样例

输入样例 1

8 3
4 4 4

输出样例 1

0 2 4

输入样例 2

10 5
7 5 1 2 3

输出样例 2

3 3 9 0 0