Running Competition
Contest: Educational Codeforces Round 93 (Rated for Div. 2)
Difficulty rating: 2600
Tags: bitmasks, fft, math, number theory

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$$$.

Input format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3 10 5
0 3 5 10
6
24 30 14 16 18 10

Example output:
24 30 14 16 -1 -1

Editorial:
First of all, let's find all possible lengths of the laps (after doing that, we can just check every divisor of $$$l_i$$$ to find the maximum possible length of a lap for a given query). A lap is always a rectangle — you can't construct a lap without using any vertical segments or using an odd number of vertical segments, and if you try to use $$$4$$$ or more vertical segments, you can't go back to the point where you started because both horizontal segments are already partially visited. So, a lap is a rectangle bounded by two vertical segments; and if we use vertical segments $$$i$$$ and $$$j$$$, the perimeter of this rectangle is $$$2(a_i - a_j + y)$$$.
Let's find all values that can be represented as $$$a_i - a_j$$$. A naive $$$O(n^2)$$$ approach will be too slow, we have to speed it up somehow. Let's build an array $$$b$$$ of $$$n + 1$$$ numbers where $$$b_j = K - a_j$$$ ($$$K$$$ is some integer greater than $$$200000$$$). Each number that can be represented as $$$a_i - a_j$$$ can also be represented as $$$a_i + b_j - K$$$, so we have to find all possible sums of two elements belonging to different arrays.
The key observation here is that, if $$$a_i$$$ and $$$b_j$$$ are small, we can treat each array as a polynomial: let $$$A(x) = \sum \limits_{i=0}^{n} x^{a_i}$$$, and similarly, $$$B(x) = \sum \limits_{j=0}^{n} x^{b_j}$$$. Let's look at the product of that polynomials. The coefficient for $$$x^k$$$ is non-zero if and only if there exist $$$i$$$ and $$$j$$$ such that $$$a_i + b_j = k$$$, so finding all possible sums (and all possible differences) can be reduced to multiplying two polynomials, which can be done faster than $$$O(n^2)$$$ using Karatsuba's algorithm or FFT.