"The Drinking Musicians", a widely known and popular folk group, are coming to your town. The musicians are known not only by their playing skills, but also their rough character. They never arrive on time, don't know which town they're in, and frequently have trouble finding the stage. Additionally, during the concert, each of the musicians at one point takes a break. If three or more of them are on a break at the same time, they start stirring trouble in town and the rest of the group start panicking and playing the wrong chords.

The concert will be T minutes long, during which each of the N members will take a break. The length of the break is known for each member.

Help the organizer of the concert by writing a program that determines how to schedule the breaks of the member so that, at any given moment, at most two are absent from the stage. All breaks must be entirely during the concert.

입력

• The first line of input contains the integers T and N (1 ≤ T ≤ 5000, 1 ≤ N ≤ 500), the length of the concert in minutes and the number of musicians in the group.
• The next line contains N integers separated by single spaces, the length of the break in minutes for each member.

출력

Output the musicians in the same order they were given in the input.

입출력 예

input 

8 3 
4 4 4 

output 

0 2 4 

input 

10 5 
7 5 1 2 3 

output 

3 3 9 0 0 

출처:coci 2006-2007 contest4