階建てのビルがあります。
やきとりくんは、このビルの 階にいます。
このビルには、 個のテレポーターがあり、テレポーター は 階に設置してあります。
テレポーターを通って他のテレポーターのある階へ移動することができますが、テレポーター を経由してテレポーター のある階へ移動するには、 の時間が必要です。
また、各階には階段があり、 つ上の階と つ下の階に の時間で移動することができます。
個のクエリが与えられます。
個目のクエリでは が与えられるので、それぞれのクエリについて、やきとりくんが 階から 階へ移動するのにかかる最小の時間を求めてください。
入力は以下の形式で標準入力から与えられる。
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
最初のクエリについて、階段のみを使って移動すると 階から 階までを の時間で移動することができます。
番目のクエリについても、階段のみを使って移動すると 階から 階までを の時間で移動することができます。
番目のクエリについては、 階から 階へ階段を使って移動し、 階から 階へテレポーターを使って移動することによって の時間で移動することができます。
100 8 38 83 5 8 12 34 57 68 88 95 5 20 40 60 80 100
1083 1439 1757 2663 2607