408487: GYM103150 A Addition Range Queries

You are given an array of $$$n$$$ integers, and you will perform $$$k$$$ operations on it.

Each operation consists of replacing each element with the sum of all the other elements. In particular, all of the following will occur simultaneously:

• For each index $$$i$$$, the element $$$a_i$$$ will be replaced with $$$a_1 + \dots + a_{i-1} + a_{i+1} + \dots + a_n$$$.

For example, applying the operation to the array $$$[1, 3, 5, 4]$$$ gives $$$[3+5+4, 1+5+4, 1+3+4, 1+3+5] = [12,10,8,9]$$$.

After applying $$$k$$$ operations to the array, find the maximum difference between any two elements of the resulting array. (The difference between two numbers $$$a$$$ and $$$b$$$ is defined as $$$|a-b|$$$.)

The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the size of the array. The second line of each test case contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

For each test case, output one integer — the maximum difference between any two elements of the resulting array.

3
4 1
1 3 5 4
1 1000
2020
10 100000
1 1 1 1 1 1 1 1 1 1

4
0
0

The first test case is described in the statement. The maximum difference occurs between the numbers $$$8$$$ and $$$12$$$.

In the second test case, there is only one number in the array, so the answer will be $$$0$$$ (regardless of the value of $$$k$$$).