Conductors

Bajtazar works as a conductor for Byteotian State Railways (BKP), famous for the longest passenger trains in all of Byteotia. Special trains call for special procedures, so the BKP board introduced rules to streamline the conductors' work. Among other things, ticket inspection proceeds as follows:

• At the start, all $n$ compartments in the train are numbered from $1$ to $n$. Likewise, each of the $k$ conductors is given a unique identifier, a number from $1$ to $k$.
• Each conductor then begins checking tickets in the compartment whose number equals their identifier.
• A conductor who finishes checking their compartment moves on to the compartment with the smallest number among those not yet checked. If two conductors finish at the same moment, the one with the smaller identifier goes first.
• If a conductor finishes a compartment and no compartments are left to check, their work is done.
• Inspection of the train ends once tickets in every compartment have been checked.

For economic reasons, the number of conductors never exceeds the number of compartments.

Every compartment in a BKP train is identical, so the time to check a single compartment depends only on the conductor's speed. Moreover, BKP values individuality, so no two conductors take the same amount of time to check a compartment.

Afterward, Bajtazar's colleagues always brag about who checked the higher-numbered compartment. Help Bajtazar find out whether he has anything to brag about: write a program that, for each conductor, determines the number of the last compartment in which they checked tickets.

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^{13}$, $1 \le k \le 100000$, $k \le n$), the number of compartments and the number of conductors, respectively.

The second line contains $k$ pairwise distinct integers $a_1, \dots, a_k$. The value $a_i$ ($1 \le a_i \le 10^5$) is the time conductor $i$ needs to check a single compartment.

On the first line, print $k$ integers: the numbers of the last compartments the conductors check, in order of increasing identifier.

The picture above shows how an inspection unfolds. Columns correspond to consecutive time units, rows to conductors, and the bold numbers to the compartment each conductor occupies at that moment.