Given a sequence of length $n$ and $m$ query operations.

Each query is given as $l\;r\;L\;R$, which means that when we keep the elements of the sequence whose values are within $[L, R]$ unchanged and set all other elements to $0$, we need to find the maximum subarray sum within the range $[l, r]$. The subarray can be empty.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence.

The following $m$ lines each contain four integers $l\;r\;L\;R$ representing a query operation.

Output

Output $m$ lines, each containing an integer representing the answer.

Examples

Input 1

6 5
-1 1 -4 5 -1 4
1 1 4 5
1 1 4 514
2 3 3 3
1 6 -1 5
2 5 2 5

Output 1

0
0
0
9
5

Note

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477

For $100\%$ of the data, $1\leq n,m \le 10^5$, and the absolute value of all numbers in the sequence is $\le 10^9$.

In the fourth query, the value range constraint is $[-1, 5]$, the sequence becomes -1 1 0 5 -1 4, the maximum subarray in the range $[1, 6]$ is $[2, 6]$, and the sum is $9$.

In the fifth query, the value range constraint is $[2, 5]$, the sequence becomes 0 0 0 5 0 4, the maximum subarray in the range $[2, 5]$ is $[4, 4]$ (tied), and the sum is $5$.