分数: 1400 点
问题陈述
Snuke 从他母亲那里得到了一个整数序列,作为生日礼物。该序列有 N 元素,以及 i- 其中第一个是 i。 Snuke 执行以下操作 Q 对此序列进行操作。的 i第一个操作,由参数描述 q_i,如下:
- 拿第一个 通过连接当前序列的无限多个副本获得的序列中的 q_i 元素,然后用这些元素替换当前序列 q_i 元素。
在这些之后 Q 运算,求每个整数的次数 1 通过 N 出现在最终序列中。
约束
- 1 ≦ N ≦ 10^5
- 0 ≦ Q ≦ 10^5
- 1 ≦ q_i ≦ 10^{18}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q q_1 : q_Q
输出
打印 N 行。的 i第行 (1 ≦ i ≦ N) 应包含整数的次数 i 出现在最后的序列中 Q 操作。
样本输入 1
5 3 6 4 11
示例输出 1
3 3 3 2 0
第一次操作后,序列变为: 1,2,3,4,5,1.
第二次操作后,序列变为: 1,2,3,4.
第三次操作后,序列变为: 1,2,3,4,1,2,3,4,1,2,3.
在此序列中,整数 1,2,3,4,5 出现 分别为 3,3,3,2,0 次。
示例输入 2
10 10 9 13 18 8 10 10 9 19 22 27
示例输出 2
7 4 4 3 3 2 2 2 0 0