Alice 和 Bill 非常喜欢玩棋盘游戏，他们总是寻找新的挑战。最近，他们发现了印尼的 Congklak 游戏，该游戏在一个由若干个装有一定数量石子的洞组成的棋盘上进行。在玩了几局之后，Alice 很快掌握了诀窍并赢得了每场比赛，因此 Bill 不想再玩了。相反，受到游戏规则的启发，他给 Alice 提出了以下挑战：
有一个棋盘，上面有 $n$ 个排成一排的洞。这些洞从左到右依次编号为 $1$ 到 $n$。最初，第 $i$ 个洞包含 $a_i$ 个石子。请注意，此设置与通常的 Congklak 游戏不同，后者的棋盘由两行和两端各一个大洞组成。
典型的 Congklak 棋盘。
现在 Bill 将进行 $t$ 轮游戏，每轮游戏的进行方式如下：
Bill 从第一个洞开始游戏，手里拿着一个新石子。然后他沿着棋盘从洞 $1$ 移动到洞 $n$。在每个洞 $i$ 处，他首先检查该洞中当前有多少个石子，并根据结果执行以下两种操作之一：
- i) 如果该洞是空的，他往里面放一个石子。接着，他检查自己手里还剩多少个石子。如果他手里没有石子了，游戏停止。否则，他接下来将手移动到洞 $i + 1$ 并重复上述步骤。
- ii) 如果该洞中至少有一个石子，他也往里面放一个石子。接着，他检查自己手里还剩多少个石子。如果他手里没有石子了，他将洞 $i$ 中的所有石子拿回手中。无论他的手是否为空，他接下来都会将手移动到洞 $i + 1$ 并重复上述步骤。
当 Bill 的手移动超过洞 $n$ 时，游戏停止，Bill 丢弃他手中仍持有的任何石子。
Bill 挑战 Alice，让她提前预测在进行完恰好 $t$ 轮游戏后，每个洞中的石子数量。请注意，在一轮游戏结束后，棋盘不会重置，即第二轮游戏的初始配置与第一轮游戏结束时的配置相同。
输入格式
输入包含以下内容：
- 第一行包含两个整数 $n$ 和 $t$（$1 \le n \le 10^5$，$1 \le t \le 10^{12}$），分别表示洞的数量和游戏轮数。
- 第二行包含 $n$ 个整数 $a_1, \dots, a_n$（$0 \le a_i \le 10^{12}$），其中 $a_i$ 表示第 $i$ 个洞中初始的石子数量。
输出格式
输出 $n$ 个整数，其中第 $i$ 个整数表示在进行 $t$ 轮游戏后，第 $i$ 个洞中的石子数量。
样例
输入样例 1
7 1 1 3 2 0 1 0 5
输出样例 1
0 4 0 1 2 1 5
输入样例 2
4 4 1000000000000 1 2 3
输出样例 2
1 3 0 5
说明
在第一个样例中，Bill 恰好进行了一轮游戏。下图展示了在这轮游戏中所执行的步骤。
图 C.1：第一个样例中 Bill 进行的唯一一轮游戏的视觉化展示。
在第二个样例中，每个洞的初始石子数量为 $[1000000000000, 1, 2, 3]$。每轮游戏后每个洞的石子数量为：
- $[0, 2, 3, 4]$
- $[1, 2, 3, 4]$
- $[0, 3, 0, 5]$
- $[1, 3, 0, 5]$