Paired Up

Problem Statement

You are given a list of $n$ integers $X = [x_1,\ x_2,\ ...,\ x_n]$. Now, imagine you have a list $P$ of all pairings of integers from $1$ to $n$ such that $P$ is sorted in increasing order. In other words, you have:

\begin{array}{rcc} P &=& \Big[\ \normalsize(1, 1), (1, 2), (1, 3), ..., (1, n),\ & & \ \ \ (2, 1), (2, 2), (2, 3), ..., (2, n), \ & & \ ...\ & & \ \ \ \ \ \ (n, 1), (n, 2), (n, 3), ..., (n, n)\ \Big]\normalsize \ \end{array}

Now, you are given $Q$ queries, each will contain a single integer $q_i$ such that $1 \leq q_i \leq |P|$, given some $q_i$ you should determine $f(q_i)$:

\begin{array}{rcl} f(k) &=& \sum_{i=1}^{k} x_{P_i[0]} - x_{P_i[1]} \end{array}

In other words, $f(k)$ takes the first $k$ pairs in $P$, and for each pair $(a, b)$ it will calculate $x_a - x_b$ and sum all of them together.

Input Format

Your first line will contain two space-separated integers $n$ and $q$

Your next line will contain $n$ space-separated integers $x_1$ through $x_n$.

Your next $Q$ lines will contain one integer each, the $i^{th}$ of which representing $q_i$.

Output Format

You should output a single integer for each query (in the same order the queries appear), the $i^{th}$ of which should be $f(q_i)$.

Constraints

• $1 \leq n, q \leq 10^5$
• $1 \leq q_i \leq n^2$
• $-10^3 \leq x_i \leq 10^3$

Sample Cases

3 3
11 7 5
4
6
9

6
8
0

Explanation 1

Here $P = [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]$.

For the first query $q_1 = 4$, we calculate $(x_1 - x_1) + (x_1 - x_2) + (x_1 - x_3) + (x_2 - x_1) = (11 - 11) + (11 - 7) + (11 - 5) + (7 - 11) = 6$. For the second query $q_1 = 6$, we calculate $(x_1 - x_1) + (x_1 - x_2) + (x_1 - x_3) + (x_2 - x_1) + (x_2 - x_2) + (x_2 - x_3)$. For the third query $q_1 = 9$, we calculate $(x_1 - x_1) + (x_1 - x_2) + (x_1 - x_3) + (x_2 - x_1) + (x_2 - x_2) + (x_2 - x_3) + (x_3 - x_1) + (x_3 - x_2) + (x_3 - x_3)$.

10 5
-5 10 -1 9 -4 6 3 -1 -7 -5
20
36
8
79
38

40
64
-57
126
80

Template

n, q = map(int, input().split())
numbers = list(map(int, input().split()))
queries = [int(input()) for _ in range(q)]

# print your output