OpenKattis
Kattis Set 08 - NP-hard Problems + Misc 1

#### Start

2021-03-08 04:00 AKST

## Kattis Set 08 - NP-hard Problems + Misc 1

#### End

2021-03-15 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -318 days 19:50:07

164:30:00

0:00:00

# Problem AMuzicari

“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 members so that, at any given moment, at most two are absent from the stage. All breaks must be entirely during the concert.

## Input

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.

## Output

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 input.

Sample Input 1 Sample Output 1
8 3
4 4 4

0 2 4

Sample Input 2 Sample Output 2
10 5
7 5 1 2 3

3 3 9 0 0