← 返回题目列表

AtCoder · agc003_e

E. 序列的顺序操作

中文机器翻译题面 查看原题

分数: 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