Problem Description

On a Saturday afternoon, Luka wakes up from his nap and remembers that there is a COCI today! Before the competition, he only has one task: to pull up the curtains.

Luka's room has \( n \) curtains, where the \( i \)-th curtain is \( a_i \) centimeters down from the top of the window. He can pull up the curtains in two ways:

• He can manually start pulling up any single curtain. Using this method, it takes him \( t \) seconds to pull up each centimeter.
• He can press a button to simultaneously pull up all curtains at the same speed.

When the button is pressed, the speed of rising curtains is defined as follows: if all curtains are rising, each curtain will rise 1 centimeter in \( s \) seconds. If \( r \) curtains are already fully raised, this slows down the system. Then, the remaining curtains will take \( s + k \cdot r \) seconds to rise each centimeter.

COCI is about to start, and Luka wants to pull up his curtains as quickly as possible. Meanwhile, his brother Marin enters the room and asks him \( q \) questions: what is the shortest time needed to ensure that the maximum drop height of the curtains does not exceed \( h \) centimeters? Marin considers the initial state of the curtains for each question.

They realize there isn't enough time to consider this problem before COCI. Fortunately, this problem is also here! Help them solve it!

Note: Luka always pulls up the curtains by an integer value in centimeters.

Input Format

The first line contains four integers \( n, t, s, k \) (\( 1 \le n, t, s \le 10^5, 0 \le k \le 10^5 \)), representing the number of curtains, the time required to manually pull up a curtain, the time required to pull up a curtain by pressing the button, and the slowdown factor for simultaneous rising.

The second line contains \( n \) integers \( a_i \) (\( 0 \le a_i \le 10^5 \)), representing the initial states of the curtains.

The third line contains an integer \( q \) (\( 1 \le q \le 10^5 \)), representing the number of questions.

The fourth line contains \( q \) integers \( h_i \) (\( 0 \le h_i \le 10^5 \)), representing the maximum curtain heights.

Output Format

Output one line with \( q \) integers, where the \( i \)-th integer represents the shortest time needed to ensure that the maximum drop height of the curtains does not exceed \( h_i \) centimeters.

Sample Input and Output

Input Sample #1

3 2 5 1
2 2 4
3
2 0 1

Output Sample #1

4 14 9

Input Sample #2

2 3 4 0
3 1
3
3 2 0

Output Sample #2

0 3 10

Input Sample #3

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

Output Sample #3

9 18 47

Notes

Sample Explanation 1

To ensure that the drop height of all curtains is at most 2 centimeters, Luka needs to manually pull up the third curtain by 2 centimeters. The fastest way is to manually pull it up, which will take him 4 seconds.

If all curtains need to be fully pulled up, Luka can first manually pull up the third curtain by 2 centimeters. Then, he can press the button to make all curtains rise simultaneously by 2 centimeters. The total time required is \( 4 + 10 = 14 \) seconds.

Similarly, if the drop height of the curtains is at most 1 centimeter, Luka will first manually pull up the third curtain by 2 centimeters, then make all curtains rise together by 1 centimeter. The total time to pull up will be 9 seconds.

Subtasks

见题面 Input 部分

见题面 Output 部分