Problem Description

At a concert, a band with $n$ musicians performs continuously for $t$ minutes, but each musician wants to rest for a certain amount of time. For the $i$-th musician, they want to rest for $a_i$ minutes. However, for overall harmony, it is not allowed for three or more musicians to be resting at the same time (but it is allowed to start one person's rest exactly when another person's rest ends).

You need to schedule the start time of each musician's rest.

Input Format

The first line contains two integers $t, n$.

The second line contains $n$ integers $a_1, \dots, a_n$, representing the desired rest duration of each musician.

Output Format

Output one line with $n$ integers, representing the scheduled start time of each musician's rest, in the same order as the input.

Note: Although the solution may not be unique, the testdata guarantees that a solution always exists, and this problem uses SPJ.

8 3
4 4 4

0 2 4

10 5
7 5 1 2 3

3 3 9 0 0

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le t \le 5000$ and $1 \le n \le 500$.

Notes

This problem is translated from COCI2007-2008 CONTEST #4 T4 MUZICARI.

Translated by ChatGPT 5