Problem Description

You are in charge of organizing an onsite contest. There are $N$ participants in this contest, numbered $1, 2, ..., N$. Participant $i$ lives at coordinate $X_i$ on the $x$-axis.

You are considering reimbursing the travel expenses for the contest participants. The reimbursement amount for participant $i$ is determined based on the contest venue's position $c$ and a reference value $d$ as follows:

• If $|X_i - c| \leq d$, then the amount is $ |X_i - c| $ yen.
• Otherwise, the amount is $ d $ yen.

You need to calculate the total travel expenses for $Q$ different candidates for the values of $c$ and $d$.

You are given integers $C_1, C_2, ..., C_Q$ and $D_1, D_2, ..., D_Q$. For each $i = 1, 2, ..., Q$, calculate the total travel expenses to be reimbursed to the participants when $c = C_i$ and $d = D_i$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ X_1 $ $ X_2 $ $ ... $ $ X_N $ $ C_1 $ $ D_1 $ $ C_2 $ $ D_2 $ $ : $ $ C_Q $ $ D_Q $

Output Format

Output $Q$ lines. The $i$-th line ($1 \leq i \leq Q$) should contain the answer when $c = C_i$ and $d = D_i$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

14
44
50

Sample Input #2

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

Sample Output #2

0
593
3000000000

Sample Input #3

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

Sample Output #3

658
759
109
0
1056

Notes/Hints

Constraints

• $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$)
• All input values are integers.

Sample Explanation 1

For example, when $c$ is set to $C_1 = 7$ and $d$ is set to $D_1 = 3$, the travel expenses for each participant would be $3$ yen, $2$ yen, $3$ yen, $3$ yen, and $3$ yen respectively. Therefore, the first line should output $3 + 2 + 3 + 3 + 3 = 14$.

见题面 Input 部分

见题面 Output 部分