相加与 MEX

题目描述

给你一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

执行以下操作 $M$ 次:

对于每个 $i\ (1 \le i \le N)$,将 $A_i$ 加上 $i$。然后,求出 $A$ 中未包含的最小非负整数。

输入格式

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

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出 $M$ 行。

第 $i$ 行 $(1 \le i \le M)$ 应包含第 $i$ 次操作后 $A$ 中未包含的最小非负整数。

样例

3 3
-1 -1 -6

2
2
0

第 1 次操作后,序列 $A$ 变为

$(-1 + 1, -1 + 2, -6 + 3) = (0, 1, -3)$。

$A$ 中未包含的最小非负整数是 $2$。

第 2 次操作后,序列 $A$ 变为

$(0 + 1, 1 + 2, -3 + 3) = (1, 3, 0)$。

$A$ 中未包含的最小非负整数是 $2$。

第 3 次操作后,序列 $A$ 变为

$(1 + 1, 3 + 2, 0 + 3) = (2, 5, 3)$。

$A$ 中未包含的最小非负整数是 $0$。

5 6
-2 -2 -5 -7 -15

1
3
2
0
0
0

数据范围

• $1 \le N,M \le 2 \times 10^5$
• $-10^9 \le A_i \le 10^9$
• 输入中的所有值均为整数。