사회적 거리 두기

Albert는 L대학에서 주최하는 Hackathon 행사 진행을 도와주기로 했는데, 사회적 거리 두기 방침에 따라 모든 참가자를 최대한 멀리 떨어뜨려 좌석을 배정하려 한다. 이를 위해 아주 긴 복도를 따라 특정 위치에 모니터, 책상, 의자를 두는 식으로 좌석을 배정하고, 각 좌석에는 최대 한 팀만 앉을 수 있다. 총 $s$개의 팀이 행사에 참가하고, 복도를 따라 총 $n$곳에 전원 공급이 가능한 콘센트가 설치되어 있다. 좌석은 반드시 콘센트가 설치된 곳에만 둘 수 있다. 편의상 콘센트가 설치된 지점들의 위치를 $x[1], x[2], \ldots, x[n]$이라 하자. 각 $x[i]$는 복도 입구로부터의 거리를 나타낸다. 즉, $i$번째 콘센트는 복도 입구로부터 $x[i]$만큼 떨어진 곳에 있다.

Albert는 $n$개의 콘센트 위치 중 $s$개를 골라 좌석을 배정하되, 가장 가까운 두 좌석 사이의 거리 $D$가 최대가 되도록 하고 싶다.

예를 들어 $n = 3$, $s = 3$이고 $x = [10, 100, 200]$이라 하자. 이때 $n = s$이므로 각 콘센트 위치에 좌석을 설치해야 한다. 가장 가까운 두 좌석 사이의 거리는 $100 - 10 = 90$이다. 다른 예로 $n = 6$, $s = 4$이고 $x = [11, 19, 24, 26, 29, 30]$이라 하자. 이때 $x[1] = 11$, $x[2] = 19$, $x[3] = 24$, $x[4] = 29$ 각각에 좌석을 설치하면 가장 가까운 두 좌석 사이의 거리는 5가 된다. $x[1] = 11$, $x[2] = 19$, $x[3] = 24$, $x[4] = 30$을 고르는 것도 가능하다. 가장 가까운 두 좌석 사이의 거리가 6 이상이 되도록 좌석 4개를 설치하는 방법은 없다.

입력으로 $n$, $s$, 그리고 $x[1], \ldots, x[n]$이 주어지면 가능한 가장 큰 $D$ 값을 출력하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄에 걸쳐 주어진다.

첫 줄에 $n$과 $s$가 공백으로 구분되어 주어진다. 다음 줄에 설치된 콘센트의 위치를 나타내는 $n$개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스에 대해 달성 가능한 최대 $D$ 값을 출력한다.

• $1 \le T \le 10$
• $2 \le s \le n \le 200,000$
• $1 \le x[i] \le 1,000,000,000$
• $x[i]$ 값은 중복되지 않는다.