Maximum Subarray Sum Query with Filtering

You are given a sequence of n integers and m queries. Each query is given in the form:

$l\; r\; L\; R$

This means that before processing the query, every element in the sequence whose value does not lie in the interval $[L,R]$ is replaced by 0. Then, on the subsequence corresponding to indices from l to r (1-indexed), you are required to compute the maximum subarray sum. Note that the subarray may be empty, and the sum of an empty subarray is defined as 0.

Note: The filtering (replacement by 0) is applied virtually for each query on the original array.

inputFormat

The first line contains two integers n and m -- the length of the sequence and the number of queries.

The second line contains n integers representing the sequence.

Each of the next m lines contains four integers l r L R representing a query.

All indices are 1-indexed.

outputFormat

For each query, output a single line containing the maximum subarray sum after filtering the sequence as per the query.

sample

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

9
7
3