{"raw_statement":[{"iden":"statement","content":"有一个由 $n$ 颗珍珠串成的项链，项链是一个环，首尾相连。其中有一颗珍珠上有特殊的记号，我们称它为**起始珍珠**。\n\n有个外星人很会发射宇宙射线，他依次发射了 $m$ 轮宇宙射线，第 $i$ 轮有一个参数 $a_i$，表示：\n\n- 外星人从起始珍珠开始数，起始珍珠是 $0$ 号，起始珍珠的下一个珍珠是 $1$ 号，以此类推（数完一圈后还会继续，例如 $n$ 号珍珠仍然是起始珍珠，$n+1$ 号珍珠是起始珍珠的下一个珍珠）。外星人会对编号为 $0,a_i,2a_i,\\dots$ 这些 $a_i$ 倍数位置上的珍珠都发射一次宇宙射线。\n\n一开始所有珍珠都是红色的，而当一个珍珠被发射宇宙射线后就会被从红色染成蓝色。\n\n你需要输出：对于每轮操作，有多少个操作前为红色的珍珠被这轮操作变成了蓝色。"},{"iden":"input","content":"第一行：两个整数 $n,m$。\n\n第二行：$m$ 个整数 $a_1,\\dots,a_m$。"},{"iden":"output","content":"第一行：$m$ 个整数，分别表示每轮操作中有多少个操作前为红色的珍珠被变为蓝色。"},{"iden":"note","content":"**【样例解释】**\n\n如图是初始时以及每次操作后各珍珠的颜色，起始珍珠编号为 $0$，可以看到，每次操作新染蓝的珍珠数量分别为 $1,1,2,0,2,0$：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/mt4dg5ap.png)\n\n---\n\n**【数据范围】**\n\n对于全部数据：$1\\leq n,m\\leq 5\\times 10^5$，$1\\leq a_i\\leq n$。\n\n|     子任务编号     |    $n\\leq$     |    $m\\leq$     |  特殊限制   | 分值 |\n| :----------------: | :------------: | :------------: | :---------: | :--: |\n| $\\text{Subtask 1}$ |     $100$      |     $100$      |     无      | $15$ |\n| $\\text{Subtask 2}$ |     $1000$     |     $1000$     |     无      | $15$ |\n| $\\text{Subtask 3}$ |     $10^5$     |     $10^5$     | $a_i\\mid n$ | $20$ |\n| $\\text{Subtask 4}$ |     $10^5$     |      $10$      |     无      | $20$ |\n| $\\text{Subtask 5}$ | $5\\times 10^5$ | $5\\times 10^5$ |     无      | $30$ |\n\n---\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/nzd79suj.png)"}],"translated_statement":null,"sample_group":[["6 6\n6 3 4 2 5 1\n","1 1 2 0 2 0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}