実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
あなたはオンサイトコンテストの運営担当者です。 このコンテストの参加者は 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)
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q X_1 X_2 ... X_N C_1 D_1 C_2 D_2 : C_Q D_Q
出力
Q 行出力せよ。 このうち i 行目 (1 \leq i \leq Q) には、c = C_i, d = D_i のときの答えを出力せよ。
入力例 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