问题陈述
N 孩子们正在排队。 最初, i前面的第一个孩子有 A_i 糖果。
您将重复以下操作 M 次。
- 给 K 糖果给糖果最少的孩子(如果有多个这样的孩子,给其中最前面的一个)。
求孩子们在 M 操作。
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^{12}
- 1 \leq K \leq 10^5
- 0 \leq A_i \leq 10^{12}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M K A_1 A_2 \ldots A_N
输出
让 B_i 是糖果的数量 i前面的第一个孩子将在 M 操作。 打印 B_1,B_2,\ldots,和 B_N 按此顺序,中间有空格。
示例输入 1
4 3 2 3 4 1 10
示例输出 1
5 4 5 10
- 的 树的 1-st 操作给糖果 3- 前面的第一个孩子。 现在,孩子们已经 3,4,3,和 10 糖果。
- 的 树的 2-nd 操作给糖果 1- 前面的第一个孩子。 现在,孩子们已经 5,4,3,和 10 糖果。
- 的 树的 3-rd 操作给糖果 3- 前面的第一个孩子。 现在,孩子们已经 5,4,5,和 10 糖果。
示例输入 2
2 1000000000000 100000 1000000000000 1
示例输出 2
50000500000000000 50000500000000001
示例输入 3
3 1415 9 26 53 58
示例输出 3
4292 4292 4288