Run Up The Building (Enhanced Version)

2 secs 1024 MB
dyktr_06's icon dyktr_06

問題文

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

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

制約

  • 2N1062 \leq N \leq 10^6
  • 1C,T1061 \leq C, T \leq 10^6
  • 2Mmin(N,105)2 \leq M \leq \min(N, 10^5)
  • 1A1<A2<<AMN1 \leq A_1 < A_2 < … < A_M \leq N
  • 1Q1051 \leq Q \leq 10^5
  • 1XiN(1iQ)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

出力

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

入出力例

入力例1
5 2 5 10
2 5
3
3
4
5
出力例1
20
30
24

最初のクエリについて、階段のみを使って移動すると 11 階から 33 階までを 2020 の時間で移動することができます。
22 番目のクエリについても、階段のみを使って移動すると 11 階から 44 階までを 3030 の時間で移動することができます。
33 番目のクエリについては、11 階から 22 階へ階段を使って移動し、22 階から 55 階へテレポーターを使って移動することによって 10+(52)2+5=2410 + (5 - 2)^2 + 5 = 24 の時間で移動することができます。

入力例2
100 8 38 83
5 8 12 34 57 68 88 95
5
20
40
60
80
100
出力例2
1083
1439
1757
2663
2607

Submit


Go (1.21)