← 返回题目列表

Codeforces · 1398/G

G. 跑步比赛

中文机器翻译题面 查看原题

一场跑步比赛即将举行。举办比赛的体育场可以用坐标平面上的几段来表示:

- 两条水平线段:一条连接点 $$$(0, 0)$$$ 和 $$$(x, 0)$$$,另一条连接点 $$$(0, y)$$$ 和 $$$(x, y)$$$;
- $$$n + 1$$$ 垂直段,编号从 $$$0$$$ 到 $$$n$$$。第 $$$i$$$ 段连接点 $$$(a_i, 0)$$$ 和 $$$(a_i, y)$$$; $$$0 = a_0 < a_1 < a_2 < \dots < a_{n - 1} < a_n = x$$$。

例如,这是一张体育场的图片,其中 $$$x = 10$$$、$$$y = 5$$$、$$$n = 3$$$ 和 $$$a = [0, 3, 5, 10]$$$:

绕圈是沿着线段行进、在同一点开始和结束且从不与自身相交的路线(绕圈中唯一重合的两个点是其起点和终点)。一圈的长度是围绕它行驶的总距离。例如,图中代表体育场的红色路线是一圈,长度为$$$24$$$。

比赛将分$$$q$$$阶段进行。第 $$$i$$$ 赛段的长度为 $$$l_i$$$,组织者希望为每个赛段选择一圈,使得该圈的长度是 $$$l_i$$$ 的除数。组织者不想为赛段选择短圈,因此对于每个赛段,他们希望找到合适的圈的最大可能长度。

帮助组织者计算各个赛段的最大可能圈数!换句话说,对于每个$$$l_i$$$,找到最大可能的整数$$$L$$$,使得$$$l_i \bmod L = 0$$$,并且存在长度恰好为$$$L$$$的一圈。

如果不可能选择这样的一圈,则打印 $$$-1$$$。

输入

第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \le n, x, y \le 2 \cdot 10^5$$$, $$$n \le x$$$)。

第二行包含 $$$n + 1$$$ 整数 $$$a_0$$$, $$$a_1$$$, ..., $$$a_n$$$ ($$$0 = a_0 < a_1 < a_2 < \dots < a_{n - 1} < a_n = x$$$)。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 阶段数。

第四行包含 $$$q$$$ 偶数整数 $$$l_1$$$, $$$l_2$$$, ..., $$$l_q$$$ ($$$4 \le l_i \le 10^6$$$) - 阶段的长度。

输出

打印 $$$q$$$ 数字。第 $$$i$$$ 个数字应等于第 $$$i$$$ 个赛段的合适单圈的最大可能长度,如果无法为该赛段选择单圈,则应等于 $$$-1$$$。

示例

输入 #1

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

输出 #1

24 30 14 16 -1 -1