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
| Subtask | Points | $n$ | $x_0$ | $m$ | Additional | Required Subtasks |
|---|---|---|---|---|---|---|
| 1 | 9 | – | – | $m = 1$ | $t_1 = 0$ | – |
| 2 | 7 | $n = 1$ | – | $m \leqslant 10\,000$ | – | – |
| 3 | 8 | $n = 2$ | – | $m \leqslant 10\,000$ | $x_1 \leqslant x_0 \leqslant x_2$ | – |
| 4 | 3 | $n \leqslant 50$ | $x_0 = 0$ | $m \leqslant 50$ | $d \leqslant 50, x_i \leqslant 50$ | – |
| 5 | 2 | $n \leqslant 50$ | $x_0 \leqslant 50$ | $m \leqslant 50$ | $d \leqslant 50, x_i \leqslant 50$ | 4 |
| 6 | 4 | – | $x_0 = 0$ | $m \leqslant 10$ | $x_i \leqslant 10^6$ | – |
| 7 | 2 | – | $x_0 \leqslant 10^6$ | $m \leqslant 10$ | $x_i \leqslant 10^6$ | 6 |
| 8 | 6 | – | $x_0 = 0$ | $m \leqslant 10\,000$ | $x_i \leqslant 10^6$ | 4, 6 |
| 9 | 10 | – | $x_0 \leqslant 10^6$ | $m \leqslant 10\,000$ | $x_i \leqslant 10^6$ | 4–8 |
| 10 | 7 | – | $x_0 \leqslant 10^6$ | $m \leqslant 10^5$ | $x_i \leqslant 10^6$ | 4–9 |
| 11 | 2 | – | – | $m \leqslant 10$ | – | 1, 6, 7 |
| 12 | 12 | – | $x_0 = 0$ | $m \leqslant 10^5$ | $d = 1$ | – |
| 13 | 5 | – | – | $m \leqslant 10^5$ | $d = 1$ | 12 |
| 14 | 8 | – | $x_0 = 0$ | $m \leqslant 10^5$ | – | 4, 6, 8, 12 |
| 15 | 2 | – | – | $m \leqslant 10^5$ | – | 1–14 |
| 16 | 1 | – | – | $m \leqslant 2 \cdot 10^5$ | – | 1–15 |
| 17 | 3 | – | – | $m \leqslant 3 \cdot 10^5$ | – | 1–16 |
| 18 | 9 | – | – | – | – | 1–17 |
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.