問題文

$N$ 階建てのビルがあります。
やきとりくんは、このビルの $1$ 階にいます。
このビルには、$M$ 個のテレポーターがあり、テレポーター $i \: (1 \leq i \leq M)$ は $A_i$ 階に設置してあります。
テレポーターを通って他のテレポーターのある階へ移動することができますが、テレポーター $u$ を経由してテレポーター $v \: (1 \leq u, v \leq M)$ のある階へ移動するには、 $(A_u - A_v)^2 + C$ の時間が必要です。
また、各階には階段があり、$1$ つ上の階と $1$ つ下の階に $T$ の時間で移動することができます。

$Q$ 個のクエリが与えられます。
$i \: (1 \leq i \leq Q)$ 個目のクエリでは $X_i$ が与えられるので、それぞれのクエリについて、やきとりくんが $1$ 階から $X_i$ 階へ移動するのにかかる最小の時間を求めてください。

制約

• $2 \leq N \leq 10^6$
• $1 \leq C, T \leq 10^6$
• $2 \leq M \leq \min(N, 10^5)$
• $1 \leq A_1 < A_2 < … < A_M \leq N$
• $1 \leq Q \leq 10^5$
• $1 \leq X_i \leq N \: (1 \leq i \leq Q)$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M C T
A_1 A_2 ... A_M
Q
X_1
X_2
...
X_Q

出力

それぞれのクエリに対する答えを改行区切りで出力せよ。

入出力例

5 2 5 10
2 5
3
3
4
5

20
30
24

最初のクエリについて、階段のみを使って移動すると $1$ 階から $3$ 階までを $20$ の時間で移動することができます。
$2$ 番目のクエリについても、階段のみを使って移動すると $1$ 階から $4$ 階までを $30$ の時間で移動することができます。
$3$ 番目のクエリについては、$1$ 階から $2$ 階へ階段を使って移動し、$2$ 階から $5$ 階へテレポーターを使って移動することによって $10 + (5 - 2)^2 + 5 = 24$ の時間で移動することができます。

100 8 38 83
5 8 12 34 57 68 88 95
5
20
40
60
80
100

1083
1439
1757
2663
2607