Primonidas 国王正在组织一场锦标赛，以寻找这片土地上最强大的角斗士。总共有 $N$ 名角斗士来到竞技场，为家乡争夺荣誉和荣耀。每位角斗士开始时都有一定的生命值（vitality）。生命值类似于生命点数，它既反映了角斗士所能承受的伤害量，也代表了他们能造成的伤害量（因为强力打击需要消耗能量）。

锦标赛共包含 $K$ 轮。每一轮中，国王会将角斗士按剩余生命值从小到大排成一列，若生命值相同则随机打破平局。Primonidas 国王认为角斗士真正的实力在于其抗击打能力，因此他命令第一位角斗士（即剩余生命值最低的那位）对第二位角斗士发动最强一击。这一击会从第二位角斗士的生命值中扣除第一位角斗士的生命值。第二位角斗士在受到攻击后，会（使用其扣除后的新生命值）对第三位角斗士发动最强一击，以此类推。这个过程一直重复，直到倒数第二位角斗士对最后一位角斗士发动最强一击（最后一位角斗士不会攻击任何人）。

请注意，在上述过程中，角斗士的生命值永远不会低于零。（生命值为零的角斗士对下一位角斗士造成的打击微不足道，不造成任何伤害。）

请输出 $K$ 轮锦标赛结束后，每位角斗士的生命值，按当前队列中从第一位到最后一位的顺序排列。

输入格式

第一行包含两个空格分隔的整数 $N$ ($2 \le N \le 10^5$) 和 $K$ ($1 \le K \le 10^{18}$)，分别表示角斗士的人数和锦标赛的轮数。

下一行包含 $N$ 个空格分隔的整数 $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$)，表示角斗士的初始生命值。

输出格式

输出 $N$ 个空格分隔的整数：锦标赛第 $K$ 轮结束后，角斗士的生命值，按他们当前站立的顺序排列。

样例

样例输入 1

6 3
21 28 24 23 1 12

样例输出 1

1 1 3 6 3 10

样例输入 2

3 1000
8 2 10

样例输出 2

0 0 2