23409번 - Absolute Pairwise Distance 다국어

John Doe invented a nice way to measure distance between two arrays of different length. Let $a_1, \ldots, a_{l_1}$ be the first array and $b_1, \ldots, b_{l_2}$ be the second one. Then $d(a, b) = \sum\limits_{i=1}^{l_1} \sum\limits_{j=1}^{l_2} |a_i - b_j|$. Unfortunately, this distance function does not satisfy the triangle inequality, but John decided to conduct a few experiments anyway.

John has a large array $a_1, \ldots, a_n$. He would like to know the values $d\left((a_{l_1}, a_{l_1+1}, \ldots, a_{r_1}), (a_{l_2}, a_{l_2+1}, \ldots, a_{r_2})\right)$ for $q$ instances of values $(l_1, r_1, l_2, r_2)$. Help him find these values.

The first line contains two integers $n$ and $q$: the number of elements in the array and the number of queries ($1 \le n, q \le 10^5$). The second line contains $n$ integers $a_1, \ldots, a_n$: the elements of John's large array ($0 \le a_i \le 10^8$). The next $q$ lines contain four integers each: $l_1$, $r_1$, $l_2$, $r_2$, which are the parameters of the respective query ($1 \le l_1 \le r_1 \le n$, $1 \le l_2 \le r_2 \le n$).

For each query, print the value of $d\left((a_{l_1}, a_{l_1+1}, \ldots, a_{r_1}), (a_{l_2}, a_{l_2+1}, \ldots, a_{r_2})\right)$.