Alley

Time limit5sMemory limit256 MB

Summary

For each k, find the smallest possible largest gap between adjacent trees after planting k more trees at integer points along the alley.

Level: Medium7 of 10
Topics: Binary search, Greedy, Math
Solved: No attempts yet

Problem

Borya recently dreamed that he was walking down a very long alley. Trees grew along it, and the distance between any two trees is an integer number of meters. A tree stands at the very beginning and at the very end of the alley.

Borya loves mathematics, so he decided to rate the beauty of the alley with a single number. He computed the largest distance between two adjacent trees. He calls this number the unevenness of the alley. The smaller the unevenness, the more beautiful the alley is in Borya's opinion.

The alley was so long that Borya's walk dragged on, and he wondered how beautiful the alley could become if he planted $k$ more trees along it. To keep the harmony, the distance between every pair of trees must be an integer number of meters. Several trees may be planted at the same point, including points where trees already grow. Help Borya find the minimum unevenness for various values of $k$ .

Input

The first line contains three integers $n$ , $m$ , and $len$ ( $2 \le n, m \le 10^6$ , $1 \le len \le 10^9$ ): the number of trees already planted, the number of values of $k$ that interest Borya, and the length of the alley.

The second line contains $n$ integers $a_1, \ldots, a_n$ ( $0 = a_1 < a_2 < \cdots < a_n = len$ ), where $a_i$ is the distance in meters from the beginning of the alley to the $i$ -th tree.

The third line contains $m$ integers $k_1, \ldots, k_m$ ( $0 \le k_i \le 10^9$ ), Borya's queries.

Output

Print $m$ real numbers, the minimum unevenness if $k_1, \ldots, k_m$ more trees are planted, respectively. Print each number on its own line.

Examples1

Example 1
Input
```
3 4 10
0 2 10
0 1 3 1000000000
```
Expected output
```
8
4
2
1
```