問題文

長さ $N$ の整数列 $A=(A_1,A_2,\\ldots,A_N)$ が与えられます。

以下の操作を $M$ 回行ってください。

• 各 $i\\ (1\\leq i \\leq N)$ について、 $A_i$ に $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$ $(1\\leq i \\leq M)$ 行目には $i$ 回目の操作後に $A$ に含まれない最小の非負整数を出力せよ。

入力例 1

3 3
-1 -1 -6

出力例 1

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$ です。

入力例 2

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

出力例 2

1
3
2
0
0
0