Distribution of Chemicals

You are given a number of departments. Each department i requires at least q_i units of chemical. In addition, a department can receive at most U extra units beyond its required q_i (i.e. the final distribution for department i, d_i, must satisfy q_i ≤ d_i ≤ q_i+U). Moreover, the final distribution must be non-decreasing (i.e. d₀ ≤ d₁ ≤ ... ≤ d_M-1) and the total distributed chemicals must equal exactly Q (formally, \(\sum_{i=0}^{M-1}d_i = Q\)). It is guaranteed that there exists at least one distribution meeting these conditions. Your task is to find any valid distribution for each test case.

Input requirements:

• The first line contains the integer T, the number of test cases.
• For each test case, the first line contains two integers: M (the number of departments) and U (the maximum extra units allowed per department).
• The next line contains M integers, representing the required quantities \(q_0, q_1, \dots, q_{M-1}\).
• The next line contains the integer Q, the total quantity to be distributed.

Output requirements:

For each test case, output one line with M space‐separated integers representing a valid non‐decreasing distribution \(d_0, d_1, \dots, d_{M-1}\) where each \(d_i = q_i + x_i\) with \(0 \le x_i \le U\), and \(\sum x_i = Q - \sum q_i\).

inputFormat

The first line contains an integer T, the number of test cases. For each test case:

1. A line with two integers M and U.
2. A line with M integers: q₀, q₁, ..., q_M-1.
3. A line with an integer Q.

It is guaranteed that there exists a sequence \(d_0, d_1, \dots, d_{M-1}\) satisfying \(q_i \le d_i \le q_i+U\), \(d_0 \le d_1 \le \cdots \le d_{M-1}\), and \(\sum_{i=0}^{M-1} d_i = Q\>.

outputFormat

For each test case, output one line containing M space‐separated integers — the valid distribution for that test case.

## sample

2
3 2
1 2 3
9
4 5
0 1 0 1
3

2 3 4
0 1 1 1

</p>