Problem Description

There is an infinitely long train with $k$ ticket inspectors. Each inspector checks $a_i$ carriages in one operation. Initially, all inspectors are at carriage $0$.

Each time, the conductor orders the leftmost inspector with the smallest index to move right by $a_i$ steps. In total, $n$ orders are given. Output, for each inspector, which order number corresponds to the final step they make.

Input Format

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

The second line contains $k$ integers $a_i$, meaning the length each inspector checks in one operation.

Output Format

Output one line with $k$ integers. The $i$-th integer means which order number corresponds to the final step made by inspector $i$.

10 3
3 5 6

10 9 7

Hint

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^{13}$, $1 \le k \le 10^5$, $k \le n$, $1 \le a_i \le 10^5$.

Translated by ChatGPT 5