Running Competition

题意翻译

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1398G/81bd381693fb1325b3353cdccb69047f4e9ca225.png) 如图。平面直角坐标系上放着一个矩形,其左下角为 $(0,0)$,右上角为 $(x,y)$。 矩形被纵向分割成 $n$ 个区域,区域的 $n+1$ 条分割线为 $x=a_i$,保证 $0=a_0<a_1<a_2<\dots<a_{n-1}<a_n=x$。 称一个矩形合法,当且仅当其仅由已有的线段构成。 $q$ 次询问,每次求出满足 $L\mid l_i$ 的最大的合法矩形周长 $L$,若不存在则输出 `-1`。

题目描述

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] $ : ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1398G/81bd381693fb1325b3353cdccb69047f4e9ca225.png)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.

输入输出样例

输入样例 #1

3 10 5
0 3 5 10
6
24 30 14 16 18 10

输出样例 #1

24 30 14 16 -1 -1