P9391 Red Strawberries

There is a necklace made of $n$ pearls. The necklace is a ring, with the head and tail connected. One pearl has a special mark, and we call it the **starting pearl**. An alien is very good at shooting cosmic rays. It shoots cosmic rays for $m$ rounds in order. In round $i$, there is a parameter $a_i$, which means: - The alien starts counting from the starting pearl. The starting pearl is numbered $0$, the next pearl is numbered $1$, and so on. After finishing one full circle, it continues counting (for example, pearl $n$ is still the starting pearl, and pearl $n+1$ is the next pearl after the starting pearl). The alien will shoot one cosmic ray at every pearl whose number is a multiple of $a_i$, i.e., pearls numbered $0, a_i, 2a_i, \dots$. At the beginning, all pearls are red. Once a pearl is hit by a cosmic ray, it will be dyed from red to blue. You need to output: for each round of operation, how many pearls that were red before this round are turned blue by this round.

The first line: two integers $n, m$. The second line: $m$ integers $a_1, \dots, a_m$.

The first line: $m$ integers, where the $i$-th integer denotes how many pearls that were red before round $i$ are turned blue in that round.

**Sample Explanation** The figure shows the colors of the pearls initially and after each operation. The starting pearl is numbered $0$. You can see that the numbers of newly dyed blue pearls in each operation are $1, 1, 2, 0, 2, 0$ respectively:  --- **Constraints** For all testdata: $1 \leq n, m \leq 5 \times 10^5$, $1 \leq a_i \leq n$. | Subtask ID | $n \leq$ | $m \leq$ | Special Restriction | Score | | :----------------: | :-------------: | :-------------: | :-----------------: | :---: | | $\text{Subtask 1}$ | $100$ | $100$ | None | $15$ | | $\text{Subtask 2}$ | $1000$ | $1000$ | None | $15$ | | $\text{Subtask 3}$ | $10^5$ | $10^5$ | $a_i \mid n$ | $20$ | | $\text{Subtask 4}$ | $10^5$ | $10$ | None | $20$ | | $\text{Subtask 5}$ | $5 \times 10^5$ | $5 \times 10^5$ | None | $30$ | ---  Translated by ChatGPT 5