問題文

あなたはオンサイトコンテストの運営担当者です。 このコンテストの参加者は N 人おり、1, 2, ..., N の番号が付けられています。 参加者 i は x 軸上の座標 X_i の位置に住んでいます。

あなたはコンテストの参加者に会場までの交通費を支給することを検討しています。 参加者 i への支給額は、コンテスト会場の位置 c と基準値 d から以下のように定めることにしています。

• |X_i - c| \leq d のとき、|X_i - c| 円
• そうでないとき、d 円

会場の位置 c と基準値 d を定めるにあたって、Q 種類のこれらの値の候補に対して、参加者に支給する交通費の合計を計算することにしました。

整数 C_1, C_2, ..., C_Q および D_1, D_2, ..., D_Q が与えられます。 i = 1, 2, ..., Q に対して、c = C_i, d = D_i としたときの参加者に支給する交通費の合計を求めてください。

制約

• 1 \leq N \leq 10^5
• 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
• X_i < X_{i + 1} (1 \leq i < N)
• 1 \leq Q \leq 10^5
• 0 \leq C_i, D_i \leq 10^9 (1 \leq i \leq Q)
• 入力値はすべて整数である。

入力例 1

5 3
1 5 10 20 30
7 3
10 20
100 10

出力例 1

14
44
50

たとえば、c の値を C_1 = 7 に、d の値を D_1 = 3 にした場合、 各参加者に交通費としてそれぞれ 3 円、2 円、3 円、3 円、3 円を支給することになります。 よって 1 行目には 3 + 2 + 3 + 3 + 3 =14 を出力します。

入力例 2

6 3
0 1 2 999999998 999999999 1000000000
0 0
100 99
1000000000 1000000000

出力例 2

0
593
3000000000

入力例 3

7 5
590 593 633 642 743 859 872
642 850108511
743 153
633 20
642 0
842 60895346

出力例 3

658
759
109
0
1056