Social Distancing

Albert has agreed to help run a Hackathon hosted by University L. Under the social distancing policy, he wants to assign seats so that all participants are as far apart as possible. To do this, he places monitors, desks, and chairs at specific positions along a very long hallway, and each seat can hold at most one team. A total of $s$ teams take part in the event, and $n$ power outlets are installed along the hallway. A seat can only be placed where an outlet is installed. For convenience, let the positions of the outlets be $x[1], x[2], \ldots, x[n]$, where each $x[i]$ is the distance from the hallway entrance. That is, the $i$-th outlet is $x[i]$ away from the hallway entrance.

Albert wants to choose $s$ of the $n$ outlet positions for seats so that the distance between the two closest seats, call it $D$, is as large as possible.

For example, let $n = 3$, $s = 3$, and $x = [10, 100, 200]$. Here $n = s$, so a seat must be placed at every outlet position. The distance between the two closest seats is $100 - 10 = 90$. As another example, let $n = 6$, $s = 4$, and $x = [11, 19, 24, 26, 29, 30]$. Placing seats at $x[1] = 11$, $x[2] = 19$, $x[3] = 24$, and $x[4] = 29$ makes the distance between the two closest seats 5. Choosing $x[1] = 11$, $x[2] = 19$, $x[3] = 24$, and $x[4] = 30$ also works. There is no way to place 4 seats so that the distance between the two closest seats is at least 6.

Given $n$, $s$, and $x[1], \ldots, x[n]$, write a program that prints the largest possible value of $D$.

The first line gives the number of test cases $T$. Each test case spans two lines.

The first line gives $n$ and $s$ separated by a space. The next line gives $n$ integers separated by spaces, the positions of the installed outlets.

For each test case, print the largest achievable value of $D$.

• $1 \le T \le 10$
• $2 \le s \le n \le 200,000$
• $1 \le x[i] \le 1,000,000,000$
• The values $x[i]$ are distinct.