公交车站

题目描述

Takahashi 起初在自己家,正要前往 Aoki 家。

两栋房子之间有编号为 $1$ 到 $N$ 的 $N$ 个公交车站,Takahashi 可以通过以下方式移动:

• 他从自己家步行到公交车站 $1$ 需要 $X$ 单位时间。
• 对于每个 $i = 1, 2, \ldots, N-1$,公交车在每个是 $P_i$ 的倍数的时刻从公交车站 $i$ 发车,乘坐该公交车需要 $T_i$ 单位时间到达公交车站 $i+1$。这里,约束保证 $1 \le P_i \le 8$。
• 他从公交车站 $N$ 步行到 Aoki 家需要 $Y$ 单位时间。

对于每个 $i = 1, 2, \ldots, Q$,处理以下查询:

求当他于时刻 $q_i$ 离开家时,能够到达 Aoki 家的最早时刻。

注意,如果他恰好在某辆公交车的发车时刻到达公交车站,他可以乘坐该公交车。

输入格式

输入按以下格式从标准输入给出。

$N$ $X$ $Y$
$P_1$ $T_1$
$P_2$ $T_2$
$\vdots$
$P_{N-1}$ $T_{N-1}$
$Q$
$q_1$
$q_2$
$\vdots$
$q_Q$

输出格式

输出 $Q$ 行。 对于每个 $i = 1, 2, \ldots, Q$,第 $i$ 行应包含第 $i$ 个查询的答案。

样例

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

34
22
710511052
136397548
763027402
644706946
447672250

对于第一个查询,Takahashi 可以如下移动,于时刻 $34$ 到达 Aoki 家。

• 于时刻 $13$ 离开家。
• 从家步行,于时刻 $15$ 到达公交车站 $1$。
• 乘坐于时刻 $15$ 从公交车站 $1$ 发车的公交车,于时刻 $19$ 到达公交车站 $2$。
• 乘坐于时刻 $24$ 从公交车站 $2$ 发车的公交车,于时刻 $30$ 到达公交车站 $3$。
• 乘坐于时刻 $30$ 从公交车站 $3$ 发车的公交车,于时刻 $31$ 到达公交车站 $4$。
• 从公交车站 $4$ 步行,于时刻 $34$ 到达 Aoki 家。

对于第二个查询,Takahashi 可以如下移动,于时刻 $22$ 到达 Aoki 家。

• 于时刻 $0$ 离开家。
• 从家步行,于时刻 $2$ 到达公交车站 $1$。
• 乘坐于时刻 $5$ 从公交车站 $1$ 发车的公交车,于时刻 $9$ 到达公交车站 $2$。
• 乘坐于时刻 $12$ 从公交车站 $2$ 发车的公交车,于时刻 $18$ 到达公交车站 $3$。
• 乘坐于时刻 $18$ 从公交车站 $3$ 发车的公交车,于时刻 $19$ 到达公交车站 $4$。
• 从公交车站 $4$ 步行,于时刻 $22$ 到达 Aoki 家。

数据范围

• $2 \le N \le 10^5$
• $1 \le X, Y \le 10^9$
• $1 \le P_i \le 8$
• $1 \le T_i \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• $0 \le q_i \le 10^9$
• 所有输入值均为整数。