Bajtazar works as a conductor for the Byteotian State Railways (BKP), which are known for having the longest passenger trains in all of Byteotia. Special trains require special solutions, which is why the BKP management has introduced regulations to streamline the work of conductors. Among other things, they state that ticket inspection proceeds as follows:

• Initially, all $n$ compartments in the train are numbered from 1 to $n$. Similarly, each of the $k$ conductors receives a unique identifier, which is a number from 1 to $k$.
• Then, each conductor begins checking tickets in the compartment with a number equal to their identifier.
• A conductor who finishes checking tickets in their current compartment begins checking tickets in the compartment with the smallest number among those that have not yet been checked. If two conductors finish checking tickets at the same time, the conductor with the smaller identifier has priority.
• If a conductor has finished checking tickets in a compartment and there are no more compartments left to check, their work is finished.
• Ticket inspection on the train is completed when tickets have been checked in all compartments.

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

All compartments in BKP trains are identical, so the time taken to check a single compartment depends only on the conductor's agility. Furthermore, BKP highly values the originality of its employees, so no two conductors check a compartment in the same amount of time.

After checking tickets on the train, Bajtazar's colleagues always boast about who checked a compartment with a higher number. Help Bajtazar determine if he has something to brag about, and write a program that determines the number of the last compartment checked by each conductor.

Input

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

The second line contains $k$ pairwise distinct integers $a_{1}, \dots, a_{k}$. The number $a_{i}$ ($1 \le a_{i} \le 10^{5}$) represents the time taken to check a single compartment by the conductor with identifier $i$.

Output

In the first line of output, your program should print $k$ integers, which are the numbers of the last compartments checked by the conductors (in order of increasing identifiers).

Examples

Input 1

10 3
3 5 6

Output 1

10 9 7

Note

The image above shows the ticket inspection process. The columns correspond to consecutive units of time, the rows to conductors, and the bold numbers to the compartment numbers where the conductors are located at a given time.