와이파이

메인 스트리트 주민들이 모든 집에 무선 인터넷을 제공하기로 하고, 무선 공유기(액세스 포인트)를 어디에 놓을지 정하는 데 도움을 청했습니다. 주민들은 모든 집에서 신호가 가능한 한 강하기를 바라지만, 예산이 한정되어 살 수 있는 공유기 수에 제한이 있습니다. 가지고 있는 공유기들을, 어떤 집이든 그 집에서 가장 가까운 공유기까지의 거리 중 최댓값이 가능한 한 작아지도록 배치하려고 합니다.

메인 스트리트는 완전히 곧은 도로입니다. 각 집의 번지수는 도로 끝에서 그 집까지의 거리(미터)와 같습니다. 예를 들어 메인 스트리트 123번지의 집은 도로 끝에서 정확히 123미터 떨어져 있습니다. 공유기는 도로 위 어느 지점에나 놓을 수 있습니다.

첫 줄에는 테스트 케이스의 개수를 나타내는 정수가 주어집니다. 각 테스트 케이스의 첫 줄에는 두 양의 정수 $n$과 $m$이 주어집니다. $n$은 주민들이 살 수 있는 공유기의 개수, $m$은 메인 스트리트에 있는 집의 개수입니다. 이어지는 $m$개의 줄에는 각각 집의 번지수가 하나씩 주어집니다. 집은 최대 100,000채이며, 각 번지수는 최대 1,000,000입니다.

각 테스트 케이스마다 한 줄에 수 하나를 출력합니다. 이는 어떤 집이든 그 집에서 가장 가까운 공유기까지의 거리 중 최댓값입니다. 이 거리를 가장 가까운 0.1미터 단위로 반올림하여 소수점 아래 정확히 한 자리로 출력하세요.