Codeforces Round 914 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

brute force

data structures

sortings

two pointers

*1400

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Array Game

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard 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.

Input

Each 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$$$.

Output

For each test case, print a single integer — the smallest possible value of the minimum of array $$$a$$$ after performing $$$k$$$ operations.

Example

Input

45 23 9 7 15 14 37 4 15 126 242 47 50 54 62 792 1500000000000000000 1000000000000000000

Output

1 0 3 500000000000000000

Note

In 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$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2024 02:21:04 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|