시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 26 11 11 42.308%

문제

As newly appointed Chief of Security, you have decided that it’s time to upgrade the border defense. There have been rumors of some neighboring countries developing nuclear weapons, so a few extra archer towers will be needed. In order to spot the miscreants when they approach, you would like to minimize the maximal distance between adjacent towers.

The border is modeled as a cyclic straight line from 0 to L, with N (old) towers placed along it. The country is an inland country, so the first and last towers are neighboring as well (consider points 0 and L to be the same). You have enough finances to place up to M new towers along the border. Find the lowest possible maximal distance between adjacent towers after the placement.

입력

The first line of input contains a single number T, the number of test cases. Then follow T lines, each describing a test case. Each test case starts with three integers N, M and L. N is the amount of towers already present at the border, M is the maximum amount of new towers you are allowed to place and L is the length of the border. Then follow N floating-point numbers ti describing the locations of the current towers.

  • 0 < T ≤ 100
  • 0 ≤ N ≤ 20000
  • 0 < M ≤ 20000
  • 0 < L ≤ 10000000
  • 0 ≤ ti < L
  • No two towers are located at the exact same location.
  • An absolute or relative error of up to 10−7 compared to the correct answer will be accepted for the distances.

출력

For each test case, output one line containing a single number, the lowest possible maximal distance between adjacent towers after the placement.

예제 입력

2
0 3 15
2 1 1000 667.4 333.8

예제 출력

5
333.6

힌트