问题描述

您是一场现场比赛的组织者。 这个比赛有 $N$ 个参与者，它们被标记为 $1, 2, ..., N$。 参与者$i$住在坐标轴上的位置 $X_i$。

您正在考虑给参赛者支付往返比赛场地的交通费用。对于参与者$i$，支付金额如下：

• 当 $|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$ 元给每个参与者。因此，我们输出 $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