题目描述

普里莫尼达斯国王正在举办一场锦标赛，以寻找全境最强的角斗士。共有 $N$ 名角斗士来到竞技场，为家乡带回荣誉与荣耀。每名角斗士初始拥有一定的活力值。活力值类似于生命值，反映了角斗士能承受的伤害量，同时也代表他们能造成的伤害量（因为强力攻击需要消耗能量）。

锦标赛包含 $K$ 轮。每一轮，国王会按照剩余活力值从低到高将角斗士排成一行，若活力值相同则随机排序。普里莫尼达斯国王认为，角斗士的真正实力在于他们的抗打击能力，因此他命令第一名角斗士（剩余活力值最低的）对第二名角斗士发动最强一击。这一击会将第一名角斗士的活力值从第二名角斗士的活力值中扣除。第二名角斗士受到攻击后，会用他们新的（降低后的）活力值对第三名角斗士发动最强一击，以此类推。此过程重复进行，直到倒数第二名角斗士对最后一名角斗士发动攻击（最后一名角斗士无需攻击任何人）。

注意在上述过程中，角斗士的活力值永远不会低于零。（活力值为零的角斗士对下一名角斗士的攻击将毫无伤害。）

输出 $K$ 轮锦标赛后每名角斗士的活力值，按当前队伍中的顺序排列。

输入格式

第一行输入包含两个以空格分隔的整数 $N$（$2 \leq N \leq 10^5$）和 $K$（$1 \leq K \leq 10^{18}$）：角斗士的数量和锦标赛的轮数。

第二行输入包含 $N$ 个以空格分隔的整数 $v_1 \; v_2 \; \ldots v_N$（$0 \leq v_i \leq 10^{18}$）：角斗士的初始活力值。

输出格式

输出 $N$ 个以空格分隔的整数：第 $K$ 轮锦标赛结束后角斗士的活力值，按当前队伍中的顺序排列。

输入输出样例 #1

输入 #1

6 3
21 28 24 23 1 12

输出 #1

1 1 3 6 3 10

输入输出样例 #2

输入 #2

3 1000
8 2 10

输出 #2

0 0 2