Cute Intervals

You are given two integer sequences (A_0, A_1, \ldots, A_{n-1}) and (B_0, B_1, \ldots, B_{n-1}) of length (n) satisfying (A_i \le B_i) for every (0 \le i < n). A subinterval ([l, r]) (with (0 \le l \le r < n)) is called cute if and only if there exists an integer sequence (C_0, C_1, \ldots, C_{n-1}) such that:

1. For all (0 \le i < n), (C_i \in [A_i, B_i]).
2. For every subinterval ([L, R]) (with (0 \le L \le R < n)) we have [ \sum_{i=L}^{R} C_i \le \sum_{i=l}^{r} C_i, ] that is, the subinterval ([l, r]) attains the maximum contiguous subarray sum of (C).

One natural strategy to guarantee ([l, r]) is the unique maximum subarray is to choose

• (C_i = B_i) for (l \le i \le r), and
• (C_i = A_i) for (i \not\in [l, r]).

With this assignment, the sum over ([l, r]) is

[ S(l,r)=\sum_{i=l}^{r} B_i, ]

and for any other subarray ([L, R]) the sum is

[ \sum_{i \in [L,R]} C_i = \sum_{i \in [L,R]\cap [l,r]} B_i + \sum_{i \in [L,R]\setminus [l,r]} A_i. ]

Thus, a sufficient and necessary condition for ([l, r]) to be cute is that

[ \sum_{i=l}^{r} B_i \ge M_{left}(l) + M_{right}(r), ]

where

• (M_{left}(l)) is the maximum contiguous subarray sum (with the possibility of being 0) in the prefix (A_0, \ldots, A_{l-1}) (if (l > 0), and defined as 0 if (l=0));
• (M_{right}(r)) is the maximum contiguous subarray sum in the suffix (A_{r+1}, \ldots, A_{n-1}) (if (r < n-1), and defined as 0 if (r=n-1)).

You are to answer (q) queries. In the (i)th query you are given four nonnegative integers (L_{1,i}), (R_{1,i}), (L_{2,i}), (R_{2,i}). You must count the number of cute intervals ([l,r]) satisfying:

• (l \in [L_{1,i}, R_{1,i}]),
• (r \in [L_{2,i}, R_{2,i}]),
• and of course (l \le r).

Implement the function as specified below.

inputFormat

The input is given in the following format (which you do not need to handle in your submission):

• The first line contains two integers (n) and (q) denoting the length of the arrays and the number of queries.
• The second line contains (n) integers: (A_0, A_1, \ldots, A_{n-1}).
• The third line contains (n) integers: (B_0, B_1, \ldots, B_{n-1}) with (A_i \le B_i) for every (i).
• The fourth line contains (q) integers representing (L_1[0], L_1[1], \ldots, L_1[q-1]).
• The fifth line contains (q) integers representing (R_1[0], R_1[1], \ldots, R_1[q-1]).
• The sixth line contains (q) integers representing (L_2[0], L_2[1], \ldots, L_2[q-1]).
• The seventh line contains (q) integers representing (R_2[0], R_2[1], \ldots, R_2[q-1]).

Note: You are required to implement the following function (without a main function):

vector maxsum(vector A, vector B, vector L1, vector R1, vector L2, vector R2);

The function should return a vector of (q) nonnegative integers, where the (i)th integer is the answer for the (i)th query.

outputFormat

The function should return a vector of (q) nonnegative integers. The (i)th integer indicates the number of cute intervals ([l, r]) (with (l \le r)) that satisfy the query constraints: (l \in [L_{1,i}, R_{1,i}]) and (r \in [L_{2,i}, R_{2,i}]).

sample

3 2
1 -1 2
3 0 4
0 0
1 2
1 0
2 2

3 5