For the first time, Polycarp’s startup ended the year with a profit! Now he is about to distribute $k$ burles as a bonus among $n$ employees.
It is known that the current salary of the $i$-th employee is $a_i$ and all the values of $a_i$ in the company are different.
Polycarp wants to distribute the $k$ burles between $n$ employees so this month the $i$-th employee will be paid not $a_i$, but $a_i+d_i$ ($d_i \ge 0$, $d_i$ is an integer), where $d_i$ is the bonus for the $i$-th employee. Of course, $d_1+d_2+\dots+d_n=k$.
Polycarp will follow two rules for choosing the values $d_i$:
- the relative order of the salaries should not be changed: the employee with originally the highest salary ($a_i$ is the maximum) should have the highest total payment after receiving their bonus ($a_i+d_i$ is also the maximum), the employee whose salary was originally the second-largest should receive the second-largest total payment after receiving their bonus and so on.
- to emphasize that annual profit is a group effort, Polycarp wants to minimize the maximum total payment to an employee (i.e minimize the maximum value of $a_i+d_i$).
Help Polycarp decide the non-negative integer bonuses $d_i$ such that:
- their sum is $k$,
- for each employee, the number of those who receive strictly more than them remains unchanged (that is, if you sort employees by $a_i$ and by $a_i+d_i$, you get the same order of employees),
- all $a_i + d_i$ are different,
- the maximum of the values $a_i+d_i$ is the minimum possible.
Help Polycarp and print any of the possible answers $d_1, d_2, \dots, d_n$.Input
The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le 10^9$) — the number of employees and the total bonus.
The second line of each test case contains $n$ different integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the current salary of the $i$-th employee.
It is guaranteed that the sum of all $n$ values in the input does not exceed $10^5$.Output
Print the answers to $t$ test cases in the order they appear in the input. Print each answer as a sequence of non-negative integers $d_1, d_2, \dots, d_n$. If there are several answers, print any of them.Exampleinput
5 4 1 3 1 4 2 2 3 10 2 4 1000000000 987654321 1000000000 999999999 500000000 8 9 5 6 1 8 3 4 2 7 6 1 6 3 1 8 5 9
output
0 0 1 0 0 3 134259259 121913582 121913582 621913577 2 2 0 2 0 1 0 2 1 0 0 0 0 0
Solution:
private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readDouble() = readLn().toDouble() // single double
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs
private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles
fun main(args: Array<String>) {
var t = readInt()
while (t-- > 0) {
var (n, k) = readInts()
var a = readInts()
var b = Array<Pair<Int, Int>>(n, {i -> Pair(a[i], i)})
b.sortWith(compareBy({it.first}, {it.second}))
var delta = IntArray(n + 1)
for (id in n-2 downTo 0) {
var i = b[id].second
var j = b[id + 1].second
var limit = minOf(a[j] - a[i] - 1, k / (id + 1))
delta[0] += limit
delta[id + 1] -= limit
k -= limit * (id + 1)
if (limit < a[j] - a[i] - 1 && k > 0) {
delta[id + 1 - k] += 1
delta[id + 1] -= 1
k = 0
}
}
delta[0] += k / n
delta[n] -= k / n
k %= n
if (k > 0) {
delta[n - k] += 1
delta[n] -= 1
}
var res = IntArray(n)
for (i in 0 until n) {
res[b[i].second] = delta[i]
delta[i + 1] += delta[i]
}
println(res.joinToString(" "))
}
}
