Problem Description

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.

Input Format

The first line: two integers $n, m$.

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

Output Format

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.

6 6
6 3 4 2 5 1

1 1 2 0 2 0

Hint

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$.

Translated by ChatGPT 5