Concert Rest Schedule

"The Drinking Musicians" is a famous band with N members. Even during a concert, its members often disappear backstage to rest.

The concert lasts for exactly T minutes. Each member i must rest exactly once during the concert, for a fixed duration of a_i minutes. If three or more members are resting at the same time, the members left on stage become too confused to continue. Therefore, at most two members may be resting at any moment.

Given every member's rest duration, determine when each member should start resting, measured in minutes after the concert begins, so that every rest finishes within the concert.

The first line contains the concert length T and the number of members N. (1 <= T <= 5000, 1 <= N <= 500)

The second line contains the rest durations of the members, in input order, separated by spaces.

Only inputs for which a valid answer exists are given. The answer may not be unique.

Print, in input order, the time at which each member should start resting. Each value is the number of minutes after the concert begins.

If member i starts at time s_i and has rest duration a_i, then 0 <= s_i and s_i + a_i <= T must hold. Also, at no time may more than two members have intervals containing that time in [s_i, s_i + a_i).

If there are multiple valid answers, print any one of them.