Running Competition
Description
A running competition is going to be held soon. The stadium where the competition will be held can be represented by several segments on the coordinate plane:
- two horizontal segments: one connecting the points $(0, 0)$ and $(x, 0)$, the other connecting the points $(0, y)$ and $(x, y)$;
- $n + 1$ vertical segments, numbered from $0$ to $n$. The $i$-th segment connects the points $(a_i, 0)$ and $(a_i, y)$; $0 = a_0 < a_1 < a_2 < \dots < a_{n - 1} < a_n = x$.
For example, here is a picture of the stadium with $x = 10$, $y = 5$, $n = 3$ and $a = [0, 3, 5, 10]$:
A lap is a route that goes along the segments, starts and finishes at the same point, and never intersects itself (the only two points of a lap that coincide are its starting point and ending point). The length of a lap is a total distance travelled around it. For example, the red route in the picture representing the stadium is a lap of length $24$.
The competition will be held in $q$ stages. The $i$-th stage has length $l_i$, and the organizers want to choose a lap for each stage such that the length of the lap is a divisor of $l_i$. The organizers don't want to choose short laps for the stages, so for each stage, they want to find the maximum possible length of a suitable lap.
Help the organizers to calculate the maximum possible lengths of the laps for the stages! In other words, for every $l_i$, find the maximum possible integer $L$ such that $l_i \bmod L = 0$, and there exists a lap of length exactly $L$.
If it is impossible to choose such a lap then print $-1$.
The first line contains three integers $n$, $x$ and $y$ ($1 \le n, x, y \le 2 \cdot 10^5$, $n \le x$).
The second line contains $n + 1$ integers $a_0$, $a_1$, ..., $a_n$ ($0 = a_0 < a_1 < a_2 < \dots < a_{n - 1} < a_n = x$).
The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of stages.
The fourth line contains $q$ even integers $l_1$, $l_2$, ..., $l_q$ ($4 \le l_i \le 10^6$) — the lengths of the stages.
Print $q$ numbers. The $i$-th number should be equal to the maximum possible length of a suitable lap for the $i$-th stage, or $-1$ if it is impossible to choose a lap for that stage.
Input
The first line contains three integers $n$, $x$ and $y$ ($1 \le n, x, y \le 2 \cdot 10^5$, $n \le x$).
The second line contains $n + 1$ integers $a_0$, $a_1$, ..., $a_n$ ($0 = a_0 < a_1 < a_2 < \dots < a_{n - 1} < a_n = x$).
The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of stages.
The fourth line contains $q$ even integers $l_1$, $l_2$, ..., $l_q$ ($4 \le l_i \le 10^6$) — the lengths of the stages.
Output
Print $q$ numbers. The $i$-th number should be equal to the maximum possible length of a suitable lap for the $i$-th stage, or $-1$ if it is impossible to choose a lap for that stage.
Samples
3 10 5
0 3 5 10
6
24 30 14 16 18 10
24 30 14 16 -1 -1