#agc003e. [agc003_e]Sequential operations on Sequence

[agc003_e]Sequential operations on Sequence

题目描述

Snuke 收到了他母亲送给他的整数序列作为生日礼物。这个序列有 NN 个元素,第 ii 个元素是 ii。Snuke 对这个序列执行以下 QQ 次操作。第 ii 次操作由参数 qiq_i 描述,操作如下:

  • 从当前序列的无限拼接中取出前 qiq_i 个元素,然后用这 qiq_i 个元素替换当前序列。

在进行完这 QQ 次操作后,计算整数 11NN 在最终序列中出现的次数。

约束条件

  • 1N1051 ≦ N ≦ 10^5
  • 0Q1050 ≦ Q ≦ 10^5
  • 1qi10181 ≦ q_i ≦ 10^{18}
  • 所有输入值都是整数。

输入

从标准输入中以以下格式给出输入:

NN QQ
q1q_1
:
qQq_Q

输出

输出 NN 行。第 ii 行(1iN1 ≦ i ≦ N)应包含整数 iiQQ 次操作后的最终序列中出现的次数。


样例输入 1

5 3
6
4
11

样例输出 1

3
3
3
2
0

在第一次操作后,序列变为:1,2,3,4,5,11,2,3,4,5,1

在第二次操作后,序列变为:1,2,3,41,2,3,4

在第三次操作后,序列变为:1,2,3,4,1,2,3,4,1,2,31,2,3,4,1,2,3,4,1,2,3

在这个序列中,整数 1,2,3,4,51,2,3,4,5 分别出现了 3,3,3,2,03,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