题目描述

There are $N$ apartment buildings equally spaced along a straight line. Building $i$ ($1 \leq i \leq N$) is located at coordinate $i \times L$ and has height $H_i$.

This year, a fireworks festival will be held, and the residents of each building want to watch the fireworks from its rooftop. However, depending on the launch position, their view may be blocked by other buildings. To avoid this, for each given launch coordinate $X_j$, determine the minimum height such that all residents can see the fireworks.

More formally, find the minimum non-negative real number $h_j$ such that there do not exist indices $a, b$ ($1 \leq a, b \leq N$) for which the line segment connecting $(a \times L, H_a)$ and $(X_j, h_j)$ (excluding endpoints) intersects with the line segment connecting $(b \times L, 0)$ and $(b \times L, H_b)$ (excluding endpoints).

输入格式

The input consists of a single test case in the following format.

$$\begin{aligned} & N \ L \ Q \\ & H_{1} \ H_{2} \ \ldots \ H_{N} \\ & X_{1} \\ & \vdots \\ & X_{Q} \end{aligned}$$

The first line contains integers $N$ ($1 \leq N \leq 300\,000$), $L$ ($1 \leq L \leq 1\,000$), and $Q$ ($1 \leq Q \leq 300\,000$), representing the number of apartment buildings, the distance between adjacent buildings, and the number of candidate launch coordinates, respectively.

The next line contains $N$ integers $H_i$ ($1 \leq H_i \leq 10^9$), representing the height of building $i$.

Each of the following $Q$ lines contains an integer $X_j$ ($-10^9 \leq X_j \leq 10^9$, $X_j \neq i \times L$ for $i = 1, \ldots, N$), representing a candidate coordinate for launching the fireworks.

输出格式

For the $Q$ queries, output the answers separated by newlines. On the $j$-th line, output the minimum launch height required when the fireworks are launched at coordinate $X_j$. The answer will be considered correct if the absolute or relative error is less than $10^{-6}$.

3 7 3
5 9 13
10
-9
28

6.7142857143
0
17