Cosmic Necklace

There is a necklace composed of $n$ pearls arranged in a circle. One of the pearls, called the \textbf{starting pearl}, is specially marked. An alien fires $m$ rounds of cosmic rays. In the $i$-th round, the alien has a parameter $a_i$, meaning that starting from the starting pearl (numbered $0$) and counting sequentially (the next pearl is $1$, and so on), the alien fires cosmic rays at the pearls in positions $0, a_i, 2a_i, \dots$. The numbering is cyclic, i.e. after reaching $n-1$, the count wraps around to $0$ again.

Initially, all pearls are red. Once a pearl is hit by a cosmic ray, if it was red, it turns blue (if it is already blue, nothing happens). For each round, output the number of pearls that were red before being hit and therefore turned blue during that round.

inputFormat

The first line contains two integers $n$ and $m$, representing the number of pearls and the number of rounds, respectively.

The second line contains $m$ space-separated integers: $a_1, a_2, \ldots, a_m$, where $a_i$ denotes the step parameter for the $i$-th round.

outputFormat

For each round, output a single line containing one integer representing the number of pearls that changed from red to blue in that round.

sample

6 2
2 3

3
1