window

题目描述

房间里有 $n$ 个百叶窗，第 $i$ 个百叶窗初始时从顶部放下 $a_i$ 厘米，所有升起操作都以整数厘米为单位。

升起百叶窗有两种方式：

1. 手动升起：可以选择任意一个百叶窗，手动升起，每升起 $1$ 厘米需要 $t$ 秒。
2. 按钮升起：按下按钮后，所有剩余的百叶窗以相同的速度并行升起，速度取决于已经完全升到顶部的百叶窗数量 $r$。如果 $r$ 个百叶窗已经升到顶，那么所有剩余的百叶窗每升起 $1$ 厘米需要 $s+k\cdot r$ 秒。

有 $q$ 个问题。每个问题：在百叶窗的初始状态下，将所有百叶窗放下高度都变为至多 $h$ 厘米所需的最小时间是多少？

输入格式

第一行包含四个整数 $n,t,s,k$，分别表示百叶窗的数量、手动升起 $1$ 厘米所需的时间、按钮并行升起 $1$ 厘米的基础时间、以及并行升起的减速因子。

第二行包含 $n$ 个整数 $a_i$，表示每个百叶窗的初始放下高度。

第三行包含一个整数 $q$，表示问题的数量。

第四行包含 $q$ 个整数 $h_i$，表示每个问题要求的最大放下高度。

输出格式

输出一行 $q$ 个整数，其中第 $i$ 个整数是使所有百叶窗的放下高度都至多为 $h_i$ 厘米所需的最小时间。

样例 1

输入

3 2 5 1
2 2 4
3
2 0 1

输出

4 14 9

样例 2

输入

2 3 4 0
3 1
3
3 2 0

输出

0 3 10

数据范围

对于所有数据，满足：

• $1\le n,t,s\le 10^5$；
• $0\le k\le 10^5$；
• $0\le a_i\le 10^5$；
• $1\le q\le 10^5$；
• $0\le h_i\le 10^5$。

评测方式

本题使用文件输入输出，程序应从 window.in 读入，并输出到 window.out。