题目描述
有一个由 n 颗珍珠串成的项链,项链是一个环,首尾相连。其中有一颗珍珠上有特殊的记号,我们称它为起始珍珠。
有个外星人很会发射宇宙射线,他依次发射了 m 轮宇宙射线,第 i 轮有一个参数 ai,表示:
- 外星人从起始珍珠开始数,起始珍珠是 0 号,起始珍珠的下一个珍珠是 1 号,以此类推(数完一圈后还会继续,例如 n 号珍珠仍然是起始珍珠,n+1 号珍珠是起始珍珠的下一个珍珠)。外星人会对编号为 0,ai,2ai,… 这些 ai 倍数位置上的珍珠都发射一次宇宙射线。
一开始所有珍珠都是红色的,而当一个珍珠被发射宇宙射线后就会被从红色染成蓝色。
你需要输出:对于每轮操作,有多少个操作前为红色的珍珠被这轮操作变成了蓝色。
输入格式
第一行:两个整数 n,m。
第二行:m 个整数 a1,…,am。
输出格式
第一行:m 个整数,分别表示每轮操作中有多少个操作前为红色的珍珠被变为蓝色。
提示
【样例解释】
如图是初始时以及每次操作后各珍珠的颜色,起始珍珠编号为 0,可以看到,每次操作新染蓝的珍珠数量分别为 1,1,2,0,2,0:

【数据范围】
对于全部数据:1≤n,m≤5×105,1≤ai≤n。
子任务编号 |
n≤ |
m≤ |
特殊限制 |
分值 |
Subtask 1 |
100 |
无 |
15 |
Subtask 2 |
1000 |
Subtask 3 |
105 |
105 |
ai∣n |
20 |
Subtask 4 |
10 |
无 |
Subtask 5 |
5×105 |
30 |
