红草莓
题目描述
有一个由 $n$ 颗珍珠串成的项链，项链是一个环，首尾相连。其中有一颗珍珠上有特殊的记号，我们称它为**起始珍珠**。
有个外星人很会发射宇宙射线，他依次发射了 $m$ 轮宇宙射线，第 $i$ 轮有一个参数 $a_i$，表示：
- 外星人从起始珍珠开始数，起始珍珠是 $0$ 号，起始珍珠的下一个珍珠是 $1$ 号，以此类推（数完一圈后还会继续，例如 $n$ 号珍珠仍然是起始珍珠，$n+1$ 号珍珠是起始珍珠的下一个珍珠）。外星人会对编号为 $0,a_i,2a_i,\dots$ 这些 $a_i$ 倍数位置上的珍珠都发射一次宇宙射线。
一开始所有珍珠都是红色的，而当一个珍珠被发射宇宙射线后就会被从红色染成蓝色。
你需要输出：对于每轮操作，有多少个操作前为红色的珍珠被这轮操作变成了蓝色。
输入输出格式
输入格式
第一行：两个整数 $n,m$。
第二行：$m$ 个整数 $a_1,\dots,a_m$。
输出格式
第一行：$m$ 个整数，分别表示每轮操作中有多少个操作前为红色的珍珠被变为蓝色。
输入输出样例
输入样例 #1
6 6
6 3 4 2 5 1
输出样例 #1
1 1 2 0 2 0
说明
**【样例解释】**
如图是初始时以及每次操作后各珍珠的颜色，起始珍珠编号为 $0$，可以看到，每次操作新染蓝的珍珠数量分别为 $1,1,2,0,2,0$：
---
**【数据范围】**
对于全部数据：$1\leq n,m\leq 5\times 10^5$，$1\leq a_i\leq n$。
| 子任务编号 | $n\leq$ | $m\leq$ | 特殊限制 | 分值 |
| :----------------: | :------------: | :------------: | :---------: | :--: |
| $\text{Subtask 1}$ | $100$ | $100$ | 无 | $15$ |
| $\text{Subtask 2}$ | $1000$ | $1000$ | 无 | $15$ |
| $\text{Subtask 3}$ | $10^5$ | $10^5$ | $a_i\mid n$ | $20$ |
| $\text{Subtask 4}$ | $10^5$ | $10$ | 无 | $20$ |
| $\text{Subtask 5}$ | $5\times 10^5$ | $5\times 10^5$ | 无 | $30$ |
---
