Problem Description

Given a sequence of length $n$, there are $m$ query operations.

Each query is in the form $l\;r\;L\;R$. It means: keep the positions whose values are in $[L,R]$ unchanged, and set all other positions to $0$. Then, compute the maximum subarray sum within the interval $[l,r]$ of the resulting sequence. This subarray is allowed to be empty.

Input Format

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

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

Then follow $m$ lines, each containing four integers $l\;r\;L\;R$, representing one query operation.

Output Format

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

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

0
0
0
9
5

Hint

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

Constraints: for $100\%$ of the testdata, $1\leq n,m \le 10^5$, and the absolute value of every number in the sequence is $\le 10^9$.

In the fourth group of queries, the value range limit is $[-1,5]$, and the sequence becomes -1 1 0 5 -1 4. The maximum subarray in interval $[1,6]$ is $[2,6]$, with sum $9$.

In the fifth group of queries, the value range limit is $[2,5]$, and the sequence becomes 0 0 0 5 0 4. The maximum subarray in interval $[2,5]$ is $[4,4]$ (tied), with sum $5$.

Translated by ChatGPT 5