Given an array A of n integers and q queries, each of the form a,b,c,d, calculate:
b∑i=ad∑j=c|Ai−Aj|
### Input
- The first line contains two integers n,q.
- The second line contains n integers Ai.
- The next q lines, each line contains four integers a,b,c,d, a query.
### Output
- Print the answer for each query.
### Constraints
- 1≤n,q≤105.
- 1≤Ai≤109.
- 1≤a≤b≤n.
- 1≤c≤d≤n.
### Example
Input:
551234511221123112412231515
Output:
136440
