题目描述

数直線上に電球が $N$ 個並んでおり、電球には左から順に $1$ から $N$ までの番号がついています。 電球 $i$ は座標 $i$ にあります。

電球には光の強さを表す非負整数値が定まっており、 座標 $x$ に光の強さ $d$ の電球があるとき、その電球は座標 $x-d-0.5$ から座標 $x+d+0.5$ までの区間を照らします。 初めは電球 $i$ の光の強さは $A_i$ です。 そこで、以下の操作を $K$ 回繰り返し行います。

• $1$ 以上 $N$ 以下の各整数 $i$ に対し、操作時に座標 $i$ を照らしている電球の個数を $B_i$ とする。そして、各電球 $i$ の光の強さを $B_i$ に変更する。

$K$ 回の操作を行った後の各電球の光の強さを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

$K$ 回の操作を行った後の電球 $i$ の光の強さ $A{'}_i$ を、以下の形式で標準出力に出力せよ。

$A{'}_1$ $A{'}_2$ $\ldots$ $A{'}_N$

题目大意

Lamps

题目描述

给定 $N$ 个灯泡，其亮度分别为 $A_i$。每个灯泡的作用范围为 $i-A_i-0.5$ 到 $i+A_i+0.5$。

有 $K$ 轮操作。

每轮操作使得每个灯泡的亮度更改为照亮它的灯泡的个数。

输入格式

输入格式如下

$N$ $K$ $A_i$

输出格式

输出更改后的 $A_i$

$A{'}_1$ $A{'}_2$ $\ldots$ $A{'}_N$

样例 #1

样例输入 #1

5 1
1 0 0 1 0

样例输出 #1

1 2 2 1 2

样例 #2

样例输入 #2

5 2
1 0 0 1 0

样例输出 #2

3 3 4 4 3

提示

数据范围

• $1\ \leqq\ N\ \leqq\ 2\ \times\ 10^5$
• $1\ \leqq\ K\ \leqq\ 2\ \times\ 10^5$
• $0\ \leqq\ A_i\ \leqq\ N$

样例1解释

$1$ 号数只有第 $1$ 个数本身作用 ，第 $2$ 个数有第 $1$ 和 第 $2$ 个数作用，以此类推。

5 1
1 0 0 1 0

1 2 2 1 2

5 2
1 0 0 1 0

3 3 4 4 3

提示

制約

• $1\ \leqq\ N\ \leqq\ 2\ \times\ 10^5$
• $1\ \leqq\ K\ \leqq\ 2\ \times\ 10^5$
• $0\ \leqq\ A_i\ \leqq\ N$

Sample Explanation 1

始めに座標 $1$ を照らしている電球は電球 $1$ のみであるので、操作後の電球 $1$ の強さは $1$ になります。 また、始めに座標 $2$ を照らしている電球は電球 $1$ と電球 $2$ であるので、操作後の電球 $2$ の強さは $2$ になります。