题目描述

有一个由 $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$ 个整数，分别表示每轮操作中有多少个操作前为红色的珍珠被变为蓝色。

6 6
6 3 4 2 5 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$。