配点 : 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