一个周六的下午，Luka 从午睡中醒来，想起今天是 COCI 比赛日！在比赛开始前，他还有一件事要做：拉起百叶窗。

Luka 的房间里有 $n$ 个百叶窗，其中第 $i$ 个百叶窗从窗户顶部向下垂了 $a_i$ 厘米。他可以通过两种方式拉起百叶窗：

• 他可以手动开始拉起任意一个百叶窗。使用这种方法，每拉起 1 厘米需要 $t$ 秒。
• 他可以按下一个按钮，这会使所有百叶窗以相同的速度并行上升。

使用按钮拉起百叶窗的速度定义如下：如果所有百叶窗都在上升，则每个百叶窗每 $s$ 秒上升 1 厘米。如果有 $r$ 个百叶窗已经升到了顶部，系统速度会变慢。此时，剩余的所有百叶窗每上升 1 厘米需要 $s + k \cdot r$ 秒。

COCI 即将开始，Luka 想尽快拉起百叶窗。与此同时，他的兄弟 Marin 走进房间问了他 $q$ 个问题：为了让所有百叶窗垂下的长度都不超过 $h$ 厘米，你最少需要多少时间？Marin 对每个问题都基于百叶窗的初始状态感兴趣。

他们意识到在 COCI 开始前没有足够的时间思考这个问题。幸运的是，这个问题也出现在了这里！帮帮他们解决它吧！

注：Luka 总是将百叶窗拉起整数厘米。

输入格式

第一行包含整数 $n, t, s$ 和 $k$ ($1 \le n, t, s \le 10^5, 0 \le k \le 10^5$)，分别表示百叶窗的数量、手动拉起百叶窗所需的时间、使用按钮拉起百叶窗所需的时间以及并行拉起时的减速因子。

第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^5$)，表示百叶窗的初始状态。

第三行包含整数 $q$ ($1 \le q \le 10^5$)，表示问题的数量。

第四行包含 $q$ 个整数 $h_i$ ($0 \le h_i \le 10^5$)，表示要求的最大垂下长度。

输出格式

仅一行，输出 $q$ 个数字，第 $i$ 个数字表示为了使百叶窗垂下长度不超过 $h_i$ 厘米，所需的最少时间。

子任务

样例

输入 1

3 2 5 1
2 2 4
3
2 0 1

输出 1

4 14 9

说明 1

为了使所有百叶窗垂下长度不超过 2 厘米，Luka 需要手动将第三个百叶窗拉起 2 厘米。最快的方法是手动拉起，这需要 4 秒。

如果所有百叶窗都需要完全拉起，Luka 可以先手动将第三个百叶窗拉起 2 厘米。现在他可以按下按钮，让所有百叶窗并行上升 2 厘米。总共需要 $4 + 10 = 14$ 秒。

同样地，如果百叶窗需要垂下长度不超过 1 厘米，Luka 将先手动将第三个百叶窗拉起 2 厘米，然后将所有百叶窗一起拉起 1 厘米。拉起百叶窗的总时间为 9 秒。

输入 2

2 3 4 0
3 1
3
3 2 0

输出 2

0 3 10

输入 3

4 3 10 3
2 4 5 6
3
4 3 0

输出 3

9 18 47