题解

题面描述

给定一个长度为$n$的序列$a$，总共进行$m$次操作，每次操作按如下规则进行：

• 在序列$a$中，找到最小元素中最靠前（下标最小）的那个，其余所有数都减去$k$。

要求输出所有操作结束后序列$a$中每个数的最终值。

题目内容

给定一个长度为$n$的序列$a$，小苯希望你在$a$上进行$m$次操作，每次操作描述为:

• 除了$a$ 中的最靠前的最小值以外的其余所有数，都会减小$k$。(注意，最小值有多个时选择最靠前，即下标最小的那个。)

现在小苯想问问你，在$m$ 次操作后，序列$a$的所有元素值分别是多少，请你求一求吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T (1≦T≦100)$代数据组数，每组测试数据描述如下:

第一行三个正整数$n,m, k(1≦n,m,k≦2×10^5)$，分别表示序列$a$的长度，操作进行的次数，以及每次操作减少的值。

第二行$n$ 个正整数$a_i(1≦a_i≦10^9)$，表示序列$a$。

除此之外，保证单个测试文件的$n$之和不超过$2×10^5$，$m$之和不超过$2×10^5$。

输出描述

对于每组测试数据:

在单独的一行输出$n$个整数，表示进行完所有操作后的序列$a$。

样例1

输入

2
6 2 3
13 11 15 20 12 11
4 1 1
1 1 1 1

输出

7 8 9 14 6 8
1 0 0 0

说明

对于第一组测试数据(每次操作选中的数字已经加粗):

初始时:$a$={$13,$11,$15,20, 12, 11$}。

操作$1$次后:$a$={1$0,11,12,17, 9$, 8}。

操作$2$次后: $a$={$7,8,9, 14,$6,$8$}。