Jihoo has two arrays $A$ and $B$ of length $N$ consisting of integers. For all integers $0 \le i \le N - 1$, the condition $A[i] \le B[i]$ is satisfied.

We define an interval $[l, r]$ as a "nice interval" if it satisfies all of the following conditions: $l, r$ are integers. $0 \le l \le r \le N - 1$. There exists an array $C$ of length $N$ consisting of integers that satisfies all of the following conditions: For all integers $0 \le i \le N - 1$, $A[i] \le C[i] \le B[i]$. * For all integers $0 \le s \le e \le N - 1$, $\sum_{i=l}^{r} C[i] \ge \sum_{i=s}^{e} C[i]$. In other words, $C[l \dots r]$ is a maximum sum subarray of $C$ (the subarray with the largest sum among all subarrays).

Jihoo is curious about how many nice intervals exist. Specifically, Jihoo's curiosity consists of $Q$ queries numbered from $0$ to $Q - 1$, which are represented by four arrays of length $Q$ consisting of integers: $L1, R1, L2, R2$.

The $j$-th query ($0 \le j \le Q - 1$) is as follows: How many nice intervals $[l, r]$ satisfy both $L1[j] \le l \le R1[j]$ and $L2[j] \le r \le R2[j]$?

You must write a program that answers Jihoo's queries.

Implementation Details

You must implement the following function:

std::vector<long long> maxsum(std::vector<int> A, std::vector<int> B,
std::vector<int> L1, std::vector<int> R1, std::vector<int> L2, std::vector<int>
R2)

• $A, B$: Arrays of integers of size $N$.
• $L1, R1, L2, R2$: Arrays of integers of size $Q$.
• This function must return an array $S$ of integers of size $Q$. For all $j$ ($0 \le j \le Q - 1$), $S[j]$ must be the answer to the $j$-th query.
• This function is called exactly once.

Constraints

• $1 \le N, Q \le 250\,000$
• $-10^9 \le A[i] \le B[i] \le 10^9$ for all integers $0 \le i \le N - 1$
• $0 \le L1[j] \le R1[j] \le N - 1$ for all integers $0 \le j \le Q - 1$
• $0 \le L2[j] \le R2[j] \le N - 1$ for all integers $0 \le j \le Q - 1$

Subtasks

1. (5 points) $1 \le N \le 500$
2. (11 points) $1 \le N \le 5\,000$
3. (45 points) $Q = 1$, $L1[0] = L2[0] = 0$, $R1[0] = R2[0] = N - 1$
4. (12 points) $L1[j] = R1[j]$ and $L2[j] = R2[j]$ for all integers $0 \le j \le Q - 1$
5. (27 points) No additional constraints.

Examples

Example 1

Consider the case where $N = 3, Q = 3, A = [-1, -1, -1], B = [2, -1, 2], L1 = [0, 0, 1], R1 = [2, 0, 2], L2 = [0, 0, 0], R2 = [2, 2, 1]$.

The grader calls the following function:

maxsum([-1, -1, -1], [2, -1, 2], [0, 0, 1], [2, 0, 2], [0, 0, 0], [2, 2, 1])

$[0, 0]$ is a nice interval because when $C = [1, -1, 0]$, $C[0 \dots 0]$ is a maximum sum subarray of $C$. $[0, 1]$ is not a nice interval because $C[1] = -1$, so for any $C$, $C[0] > C[0] + C[1]$. In a similar way, it can be proven that the only nice intervals are $[0, 0], [0, 2], [1, 1], [2, 2]$. Therefore, the function should return $[4, 2, 1]$.

Sample grader

The sample grader receives input in the following format:

• Line 1: $N \ Q$
• Line $2 + i$ ($0 \le i \le N - 1$): $A[i] \ B[i]$
• Line $N + 2 + j$ ($0 \le j \le Q - 1$): $L1[j] \ R1[j] \ L2[j] \ R2[j]$

The sample grader outputs the following:

• Line 1: If $S$ is the return value of the function maxsum, $S[0] \ S[1] \dots S[Q - 1]$

Note that the sample grader may differ from the grader used in actual evaluation.