C. Array Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a of n positive integers. In one operation, you must pick some (i, j) such that 1\leq i < j\leq |a| and append |a_i - a_j| to the end of the a (i.e. increase n by 1 and set a_n to |a_i - a_j|). Your task is to minimize and print the minimum value of a after performing k operations.InputEach test contains multiple test cases. The first line contains an integer t (1 \leq t \leq 1000) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers n and k (2\le n\le 2\cdot 10^3, 1\le k\le 10^9) — the length of the array and the number of operations you should perform.The second line of each test case contains n integers a_1, a_2, \ldots, a_n (1\le a_i\le 10^{18}) — the elements of the array a.It is guaranteed that the sum of n^2 over all test cases does not exceed 4\cdot 10^6.OutputFor each test case, print a single integer — the smallest possible value of the minimum of array a after performing k operations.ExampleInput
45 23 9 7 15 14 37 4 15 126 242 47 50 54 62 792 1500000000000000000 1000000000000000000Output
1
0
3
500000000000000000
NoteIn the first test case, after any k=2 operations, the minimum value of a will be 1.In the second test case, an optimal strategy is to first pick i=1, j=2 and append |a_1 - a_2| = 3 to the end of a, creating a=[7, 4, 15, 12, 3]. Then, pick i=3, j=4 and append |a_3 - a_4| = 3 to the end of a, creating a=[7, 4, 15, 12, 3, 3]. In the final operation, pick i=5, j=6 and append |a_5 - a_6| = 0 to the end of a. Then the minimum value of a will be 0.In the third test case, an optimal strategy is to first pick i=2, j=3 to append |a_2 - a_3| = 3 to the end of a. Any second operation will still not make the minimum value of a be less than 3.
45 23 9 7 15 14 37 4 15 126 242 47 50 54 62 792 1500000000000000000 1000000000000000000
1 0 3 500000000000000000 
['binary search', 'brute force', 'data structures', 'sortings', 'two pointers', '*1400']