“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
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 members so that,
at any given moment, at most two are absent from the stage. All
breaks must be entirely during the
The first line of input contains the integers $T$ and $N$ ($1
\le T \le 5000$, $1 \le N
\le 500$), the length of the concert in minutes and the
number of musicians in the group.
The next line contains $N$ integers (each between
$1$ and $T$ inclusive) separated by single
spaces, the length of the break in minutes for each member.
Note: The input data will be such that a solution, although
not necessarily unique, will always exist.
For each musician output one integer, the number of minutes
the musician will spend on stage before going on the break.
Output the musicians in the same order they were given in the
|Sample Input 1
||Sample Output 1
4 4 4
0 2 4
|Sample Input 2
||Sample Output 2
7 5 1 2 3
3 3 9 0 0