Running Competition

题意翻译

跑步比赛马上就要开始了。举行比赛的体育场可以用坐标平面上的几个部分来表示:  一圈是沿着线段的路线，起点和终点在同一点，并且从来没有交叉(一圈中只有两点重合是它的起点和终点)。一圈的长度是围绕它运行的总距离。例如，图中代表体育场的红色路线是24 组织者不想在每个阶段都选短圈，所以对于每个阶段，他们想找到合适圈的最大长度。 请你帮助组织者计算各个赛段最大的圈长!

题目描述

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.

输入输出样例

输入样例 #1

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

输出样例 #1

24 30 14 16 -1 -1

题意翻译

跑步比赛马上就要开始了。举行比赛的体育场可以用坐标平面上的几个部分来表示:  一圈是沿着线段的路线，起点和终点在同一点，并且从来没有交叉(一圈中只有两点重合是它的起点和终点)。一圈的长度是围绕它运行的总距离。例如，图中代表体育场的红色路线是24 组织者不想在每个阶段都选短圈，所以对于每个阶段，他们想找到合适圈的最大长度。 请你帮助组织者计算各个赛段最大的圈长!