题目描述

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