Given two sequences filled with non-negative integers, $A$ and $B$, of length $N$, you will answer $Q$ queries, each consisting of two numbers, $l_i$ and $r_i$. For each query, find a $K$ where $l_i\le K\le r_i-1$ that will minimize $max(A_{l_i}+A_{l_i+1}+\cdots +A_{K-1}+A_K,B_{K+1}+B_{K+2}+\cdots +B_{r_i-1}+B_{r_i})$ and output the minimized value.

Constraints

For all subtasks:

$2\le N\le 2\times {10}^5$

$1\le Q\le 2\times {10}^5$

$1\le l_i<r_i\le N$

$0\le A_i,B_i\le {10}^9$

Subtask 1 [20%]

$2\le N\le 5\times {10}^3$

$1\le Q\le 5\times {10}^3$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line consists of two integers $N$ and $Q$, the length of the sequences and the number of queries.

The next two lines consist of $N$ integers.

The following $Q$ lines consist of two integers $l_i$ and $r_i$.

Output Specification

Output the minimized value for each query on $Q$ separate lines.

Sample Input

4 4
7 5 3 5
6 2 9 1
1 2
2 3
3 4
1 2

Sample Output

7
9
3
7