시간 제한메모리 제한제출정답맞힌 사람정답 비율
5.5 초 (추가 시간 없음) 512 MB111100.000%

문제

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)$.

예제 입력 1

5 5
1 2 3 4 5
1 1 2 2
1 1 2 3
1 1 2 4
1 2 2 3
1 5 1 5

예제 출력 1

1
3
6
4
40