問題文

ローマのとある郊外に，1 本の十分に長い線路がある．この線路は数直線とみなすことができ，線路沿いの各地点は 1 個の整数による座標で表される． この線路に沿って N 個の駅があり，座標の小さい順に 1 から N までの番号が付けられている．駅 i (1 \leqq i \leqq N) の位置は座標 A_i である．2 つ以上の駅が同じ座標に存在することはない．

この線路上を列車が走っている．列車は座標が小さい地点から大きい地点に向かう方向にのみ運行しており，すべての駅に停車する．

運賃は乗車駅と降車駅の距離に応じて決まり，ある整数列 (B_1, B_2, ..., B_K) を用いて以下のように計算される．ここで，1 = B_1 < B_2 < \cdots < B_K が成り立つ．なお，乗車駅と降車駅は相異なる必要がある．

• 乗車駅と降車駅の距離を d (d\geqq 1) とし，B_j \leqq d を満たす最大の整数 j (1 \leqq j \leqq K) を j_\text{max} とする．このとき，運賃は j_\text{max} である．

イタリア観光に来たビ太郎は，この列車に Q 回乗車する計画があり，各回の運賃を計算しようと思っている． k 回目 (1 \leqq k \leqq Q) の乗車計画では，列車に乗って駅 l_k から駅 r_k まで行きたいと思っている．ここで，l_k < r_k である．

ビ太郎は疲れているので，列車に乗らず駅の間を移動することはしない．しかし，途中下車して運賃を一度精算し，再度その駅から乗車することはできる． 途中下車はどの駅でも可能であり，回数に制限はない． 例えば，駅 s_1, s_2, \cdots, s_m で途中下車した場合 (l_k < s_1 < s_2 < \cdots < s_m < r_k)，距離 A_{s_1} - A_{l_k}, A_{s_2} - A_{s_1}, A_{s_3} - A_{s_2}, \cdots, A_{s_m} - A_{s_{m-1}}, A_{r_k} - A_{s_m} の分の運賃を支払うことになる．

ビ太郎は適切に途中下車することで，駅 l_k から駅 r_k まで行くのに必要な運賃の合計を最小化したい．

駅と運賃と乗車計画の情報が与えられたとき，それぞれの乗車計画について，ビ太郎が支払う必要のある運賃の合計の最小値を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 150\,000．
• 1 \leqq A_1 < A_2 < \cdots < A_N \leqq 10^9．
• 1 \leqq K \leqq 20．
• 1 = B_1 < B_2 < \cdots < B_K \leqq 10^9．
• 1 \leqq Q \leqq 150\,000．
• 1 \leqq l_k < r_k \leqq N (1 \leqq k \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (8 点) K \leqq 2．
2. (11 点) N \leqq 500．
3. (29 点) Q = 1．
4. (20 点) K \leqq 5．
5. (32 点) 追加の制約はない．

入力例 1

8
1 3 4 5 8 9 12 14
8
1 2 5 6 7 9 10 11
3
1 5
3 5
1 7

出力例 1

4
2
6

1 回目の乗車計画では，ビ太郎は列車に乗って駅 l_1=1 から駅 r_1=5 まで行きたいと思っている． このとき，例えば以下のように行動することができる．

• まず，駅 1 で乗車し，駅 3 で途中下車する．このときの乗車距離は A_3 - A_1 = 3 であり，B_j \leqq 3 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．
• 次に，駅 3 で再度乗車し，駅 5 で降車する．このときの乗車距離は A_5 - A_3 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．

この場合の運賃の合計は 2 + 2 = 4 であり，これより運賃の合計を小さくすることはできない．よって，1 行目に 4 を出力する．

2 回目の乗車計画では，ビ太郎は列車に乗って駅 l_2=3 から駅 r_2=5 まで行きたいと思っている． このとき，例えば以下のように行動することができる．

• 駅 3 で乗車し，駅 5 で下車する．このときの乗車距離は A_5 - A_3 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．

この場合の運賃の合計は 2 であり，これより運賃の合計を小さくすることはできない．よって，2 行目に 2 を出力する．

3 回目の乗車計画では，ビ太郎は列車に乗って駅 l_3=1 から駅 r_3=7 まで行きたいと思っている． このとき，例えば以下のように行動することができる．

• まず，駅 1 で乗車し，駅 4 で途中下車する．このときの乗車距離は A_4 - A_1 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．
• 次に，駅 4 で再度乗車し，駅 6 で途中下車する．このときの乗車距離は A_6 - A_4 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．
• 次に，駅 6 で再度乗車し，駅 7 で降車する．このときの乗車距離は A_7 - A_6 = 3 であり，B_j \leqq 3 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．

この場合の運賃の合計は 2 + 2 + 2 = 6 であり，これより運賃の合計を小さくすることはできない．よって，3 行目に 6 を出力する．

この入力例は小課題 2,5 の制約を満たす．

入力例 2

10
3 6 16 19 32 40 41 53 59 78
2
1 15
1
3 10

出力例 2

2

この入力例はすべての小課題の制約を満たす．

入力例 3

10
11 13 39 42 53 54 66 69 77 83
15
1 5 13 31 40 41 52 57 59 66 70 79 97 103 115
5
1 6
2 9
1 8
2 7
3 9

出力例 3

6
7
6
6
4

この入力例は小課題 2,5 の制約を満たす．