Guarding the Border

Interview

Time limit3sMemory limit256 MB

Summary

Add up to M towers anywhere on a circular border of length L so the largest gap between neighboring towers is as small as possible.

Level: Medium5 of 10
Topics: Binary search, Greedy, Sorting
Solved: No attempts yet

Problem

As the newly appointed chief of security, you have decided to upgrade the border defense. Neighbouring countries are rumoured to be building nuclear weapons, so a few more archer towers are needed. To spot intruders while they are still approaching, you want the largest distance between two adjacent towers to be as small as possible.

The border runs from $0$ to $L$ and closes on itself, so treat it as a loop of circumference $L$ . The country is landlocked, so the first and the last tower are neighbours as well: the coordinates $0$ and $L$ are the same place. $N$ old towers already stand on the border. The budget pays for at most $M$ new towers, and you may put each of them anywhere on the border, not only at an integer coordinate. After the placement, find the smallest possible value of the largest distance between two adjacent towers.

If a single tower stands on the loop, it is its own neighbour and the distance between adjacent towers is $L$ .

Input

The first line contains the number of test cases $T$ . Each of the following $T$ lines describes one test case. A line starts with three integers $N$ , $M$ and $L$ . $N$ is the number of towers already standing on the border, $M$ is the largest number of new towers you may place, and $L$ is the length of the border. The $N$ positions $t_i$ of the current towers follow on the same line.

$0 < T \le 100$
$0 \le N \le 20000$
$0 < M \le 20000$
$0 < L \le 10000000$
$0 \le t_i < L$ , written with at most 6 digits after the decimal point
No two towers stand at the same position.

Output

For each test case print one line with the smallest possible value of the largest distance between two adjacent towers, rounded to exactly 6 digits after the decimal point. An answer of $5$ is printed as 5.000000. Every answer in the test data is more than $10^{-9}$ away from a point where the rounding direction changes, so double precision arithmetic produces the same output.

Examples7

Example 1

Input

2
0 3 15
2 1 1000 667.4 333.8

Expected output

5.000000
333.600000

Example 2
Input
```
1
1 1 10 0.0
```
Expected output
```
5.000000
```

Example 3

Input

3
0 1 10000000
0 20000 10000000
0 3 10

Expected output

10000000.000000
500.000000
3.333333

Example 4
Input
```
1
3 4 100 0.0 10.0 30.0
```
Expected output
```
17.500000
```
Example 5
Input
```
1
3 1 100 10.0 20.0 30.0
```
Expected output
```
40.000000
```

Example 6

Input

1
5 3 50 40.5 2.25 33.0 11.75 49.999999

Expected output

9.499999

Example 7

Input

1
4 5 7 0.000001 1.234567 3.999999 6.5

Expected output

0.921811