A new attraction has opened in Sochi Park. There are $n$ targets located along a straight line, with the $i$-th target at coordinate $x_i$ ($1 \leqslant i \leqslant n$). Visitors must hit all these targets in any order.

Balls are used to hit the targets. If a visitor is at a point with coordinate $x$ and wants to hit a target located at $x_i$, they must spend $(x - x_i)^2$ calories.

A visitor enters the attraction at a point with coordinate $x_0$. There is an unlimited supply of balls at the entry point, as well as at all points at a distance $d$ from each other, i.e., at points $x_0 + kd$, where $k$ is an arbitrary integer. Moving balls is prohibited by the attraction's rules, so they can only be thrown from these points.

During the day, $m$ Olympiad participants will visit Sochi Park. The participants are in different physical shape, so the $j$-th participant needs $t_j$ calories to move a distance $d$.

You need to determine the minimum number of calories required for each participant to hit all the targets of the attraction.

Input

The first line contains a single integer $n$ ($1 \leqslant n \leqslant 3 \cdot 10^5$) — the number of targets in the attraction. The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \leqslant x_i \leqslant 10^9$) — the coordinates of the targets. The third line contains two integers $x_0$ and $d$ ($0 \leqslant x_0 \leqslant 10^9$, $1 \leqslant d \leqslant 2 \cdot 10^6$) — the entry point of the attraction and the distance between the locations of the ball supplies. The fourth line contains a single integer $m$ ($1 \leqslant m \leqslant 6 \cdot 10^5$) — the number of Olympiad participants. The following $m$ lines each contain a single integer $t_j$ ($0 \leqslant t_j \leqslant 10^8$) — the amount of energy required for the $j$-th participant to move between two adjacent ball supply locations.

Output

For each Olympiad participant, output a single integer — the minimum number of calories required for them to move and hit all targets.

Given these constraints, the answer does not exceed the maximum value of a 64-bit signed integer type. However, for intermediate calculations, you may need the __int128 data type in C++ (only supported in the GNU C++ compiler), BigInteger in Java, or int in Python.

Subtasks

Examples

Input 1

3
4 0 7
2 3
7
0
1
2
3
4
23
25

Output 1

3
7
10
12
13
32
33

Input 2

4
30 239 57 179
0 7
5
1
10
15
100
100000

Output 2

49
355
525
3378
93311

Input 3

4
100 2 101 666
9 10
5
777
1
2
15
10

Output 3

49597
91
159
1043
703

Note

In the first test, for the second participant ($t_2 = 1$), the optimal algorithm for hitting the targets is: 1. Move from $x_0 = 2$ to $x_0 - d = -1$, spending $t_2 = 1$ calorie. Note that the visitor's coordinate can be negative. 2. Hit the target at $x_2 = 0$, spending $(-1 - 0)^2 = 1$ calorie. 3. Move to $x_0 - d + 2d = 5$, spending $2t_2 = 2$ calories. 4. Hit the target at $x_1 = 4$, spending $(5 - 4)^2 = 1$ calorie. 5. Move to $x_0 + d = 8$, spending $t_2 = 1$ calorie. 6. Hit the target at $x_3 = 7$, spending $(8 - 7)^2 = 1$ calorie.

The total energy expenditure is $1 + 2 + 1 + 1 + 1 + 1 = 7$ calories. It can be shown that this is the minimum amount of energy.

For the sixth participant ($t_6 = 23$), the optimal algorithm for hitting the targets is: 1. Hit the target at $x_2 = 0$, spending $(2 - 0)^2 = 4$ calories. 2. Move to $x_0 + d = 5$, spending $t_6 = 23$ calories. 3. Hit the target at $x_3 = 7$, spending $(7 - 5)^2 = 4$ calories. 4. Hit the target at $x_1 = 4$, spending $(5 - 4)^2 = 1$ calorie.

The total energy expenditure is $4 + 23 + 4 + 1 = 32$ calories. It can be shown that this is the minimum amount of energy.