The company is in the business of creating coding test problems and selling them to IT companies, thanks to the recent surge in the popularity of coding tests.

For convenience, the company has categorized the difficulty of the problems it creates from level $0$ to level $N-1$. Currently, the company has $A[i]$ problems prepared that are rated at level $i$, and $B[i]$ problems that are rated at either level $i$ or level $i+1$ because their difficulty is ambiguous. There are no problems rated in any other way.

The company is currently looking for companies to sell these problems to. There are $M$ companies interested in purchasing, numbered from $0$ to $M-1$. Company $j$ ($0 \le j \le M-1$) is only interested in problems with a difficulty level between $L[j]$ and $U[j]$ inclusive.

When selling problems to company $j$, the company intends to sell them in sets, where each set consists of one problem of each difficulty level from $L[j]$ to $U[j]$. Let this be called a "set."

If the company only sells problems to company $j$, what is the maximum number of sets it can sell?

For problems rated at level $i$ or $i+1$, you must appropriately assign them to one of the two levels to maximize the number of sets sold, ensuring that the same problem is not included multiple times across all sold sets.

Implementation Details

You must implement the following function:

vector<int> testset(vector<int> A, vector<int> B, vector<int> L, vector<int> U)

• This function is called exactly once.
• $A$: An integer array of length $N$. For all $i$ ($0 \le i \le N-1$), $A[i]$ is the number of problems rated at level $i$.
• $B$: An integer array of length $N-1$. For all $i$ ($0 \le i \le N-2$), $B[i]$ is the number of problems rated at either level $i$ or level $i+1$.
• $L, U$: Integer arrays of length $M$. For all $j$ ($0 \le j \le M-1$), $L[j]$ and $U[j]$ are the minimum and maximum difficulty levels desired by company $j$, respectively.
• This function must return an integer array $S$ of length $M$. For all $j$ ($0 \le j \le M-1$), $S[j]$ is the maximum number of sets consisting of problems with difficulty levels from $L[j]$ to $U[j]$ that can be sold to company $j$.

You must not execute any input/output functions in any part of your submitted source code.

Examples

Input 1

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

Output 1

3
5

Note

Company 0 wants problems with a difficulty level between 0 and 3. It is possible to create 3 sets, and it is impossible to create more sets as only one problem of level 1 remains.

Company 1 wants problems with a difficulty level between 1 and 2. It is possible to create 5 sets, and it is impossible to create more sets using all available problems.

Constraints

• $2 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• $0 \le A[i] \le 10^8$ (for all $0 \le i \le N-1$)
• $0 \le B[i] \le 10^8$ (for all $0 \le i \le N-2$)
• $0 \le L[j] \le U[j] \le N-1$ (for all $0 \le j \le M-1$)

Subtasks

1. (3 points) $A[i] \le 1\,000$ ($0 \le i \le N-1$), $B[i] \le 1\,000$ ($0 \le i \le N-2$), $U[j] - L[j] \le 2$ ($0 \le j \le M-1$)
2. (15 points) $M \le 100$
3. (36 points) $N \le 5\,000$
4. (23 points) $L[j] = 0$ (for all $0 \le j \le M-1$)
5. (23 points) No additional constraints

Sample grader

The sample grader receives input in the following format:

• Line 1: $N \ M$
• Line 2: $A[0] \ A[1] \ \dots \ A[N-1]$
• Line 3: $B[0] \ B[1] \ \dots \ B[N-2]$
• Line $4 + j$ ($0 \le j \le M-1$): $L[j] \ U[j]$

The output format of the sample grader is as follows:

• Line $1 + j$ ($0 \le j \le M-1$): $S[j]$