# [solution] Wishcraft solution codechef

## Problem solution codechef

Magic is really very simple, all you’ve got to do is want something and then let yourself have it.

Chadda and his Wizard friend PSC were exploring the enchanted forest on Halloween, when Chadda stumbled upon an array  of  magical numbers which took him into a different world.

Chadda remembered that PSC gave him two integers  and  for such a situation.
Using these integers, Chadda can modify the array  as follows:

• At most  times, perform the following operation:
• Pick two elements  and  from , delete them both from , and insert (�+�) into .
This operation can be performed only if  has at least two elements.
• At most  times, perform the following operation:
• Pick two elements  and  from , delete them both from , and insert (�−�) into .
This operation can also be performed only if  has at least two elements.

Note that each operation reduces the size of  by one.
The two types of operations (addition and subtraction) can be performed in any order, as long as at most  addition operations and  subtraction operations are made.

Let  denote the final array obtained after performing some (possibly, zero) operations.

max⁡(�)−min⁡(�)

across all possible final arrays .
Can you help Chadda find this value?

### Input Format

• The first line of input will contain a single integer , denoting the number of test cases.
• Each test case consists of three lines of input.
• The first line of each test case contains a single integer  — the size of the array.
• The second line contains two space-separated integers  and  — the maximum number of addition and subtraction operations, respectively.
• The third line contains  space-separated integers �1,�2,…,��: the elements of array .

### Output Format

For each test case, output on a new line the answer: the maximum possible value of max⁡(�)−min⁡(�) across all possible final arrays .

### Constraints

• 1≤�≤105
• 1≤�≤105
• 0≤�,�≤�−1
• −109≤��≤109
• The sum of  over all test cases won’t exceed 3⋅105.

### Sample 1:

Input

Output

3
2
0 0
5 1
6
1 2
8 -1 -4 2 6 -3
7
6 6
-2 -4 2 -2 -3 -1 -1
4
23
15

### Explanation:

Test case 1: �=�=0, so no operations can be performed at all.

Test case 2: The array is �=[8,−1,−4,2,6,−3]. The following sequence of operations can be performed:

• Choose 2 and −3, remove them, and insert 2−(−3)=5 into the array.
The elements are now [8,−1,−4,6,5].
• Choose 8 and 5, remove them, and add 8+5=13 to the array.
The elements are now [13,−1,−4,6].
• Choose −4 and 6, remove them and add (−4)−(6) to the array.
The elements are now [13,−1,−10].

The difference between maximum and minimum for this array is 13−(−10)=23.
With one addition and two subtraction operations available, it can be proved that this is the maximum attainable value.

Test Case 3:: It can be proven that 15 is the maximum attainable value