← 返回题目列表

AtCoder · abc272_e

H. 添加和墨西哥

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

分数: 500 点

问题陈述

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

执行以下操作 M 次:

  • 对于每个 i\ (1\leq i \leq N),添加 i to A_i。 然后,找到不包含在其中的最小非负整数 A.

约束

  • 1\leq N,M \leq 2\times 10^5
  • -10^9\leq A_i\leq 10^9
  • 输入中的所有值都是整数。

输入

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

N M 
A_1 A_2 \ldots A_N

输出

打印 M 行。

的 i-th (1\leq i \leq M) 行应包含未包含在的最小非负整数 A 之后 i第次操作。


示例输入 1

3 3
-1 -1 -6

示例输出 1

2
2
0

的 1-st 操作使序列 A

(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).

不包含在的最小非负整数 A is 2.

的 2-nd 操作使序列 A

(0 + 1, 1 +2 ,-3+3) = (1,3,0).

不包含在的最小非负整数 A is 2.

的 3-rd 操作使序列 A

(1 + 1, 3 +2 ,0+3) = (2,5,3).

不包含在的最小非负整数 A is 0.


示例输入 2

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

示例输出 2

1
3
2
0
0
0