Given an array $A$ of $n$ integers and $q$ queries, each of the form $a, b, c, d$, calculate:
$$
\sum_{i=a}^{b} \sum_{j=c}^{d}|A_i-A_j|
$$
### Input
- The first line contains two integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines, each line contains four integers $a, b, c, d$, a query.
### Output
- Print the answer for each query.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le A_i \le 10^9$.
- $1 \le a \le b \le n$.
- $1 \le c \le d \le n$.
### Example
Input:
```
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
```
Output:
```
1
3
6
4
40
```
