该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个长度为 $m$的序列 $A_1,A_2,...,A_m$ ，序列 $A$ 的数字都在 $1$ 到 $n−1$ 的范围内，然后还有一个序列 $B_1,B_2,...,B_n$ ，一开始，序列 $B$ 的数字满足 $B_i=i$。现在对于每一个 $i=1,2,3,...,m$ ，我们会对序列 $B$ 进行一次 $k=1,2,3,...,i−1,i+1,...,m$ 的变换操作，变换中要交换序列 $B$ 的第 $A_k$ 个和第 $A_k+1$ 个元素。序列 $B$ 变换后 $1$ 的位置记为 $S_i$ ，对于每个 $i$ ，输出 $S_i$ 。

输入格式

第一行，两个正整数 $n,m$ 。

第二行输入 $m$ 个整数 $A_1,A_2,...,A_m$ 。

输出格式

输出 $m$ 行，第 $i$ 行输出 $S_i$ 。

样例 #1

样例输入 #1

5 4
1 2 3 2

样例输出 #1

1
3
2
4

当 $i=2$ 时，需要进行 $k=1,3,4$ 的变换，即交换 $B_1,B_2$ ，交换 $B_3,B_4$ ，交换 $B_2,B_3$ ，最后得到新的序列 $B=(2,4,1,3,5)$ ，可发现 $B_3=1$ ，所以答案 $S_2=3$。

样例 #2

样例输入 #2

3 3
2 2 2

样例输出 #2

1
1
1

样例 #3

样例输入 #3

10 10
1 1 1 9 4 4 2 1 3 3

样例输出 #3

2
2
2
3
3
3
1
3
4
4

提示

【数据范围】

对于 $100$ 的数据：

• $2≤n≤2×10^5$
• $1≤m≤2×10^5$
• $1≤A_i≤n−1(1≤i≤m)$
• 所有数字都是整数