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} + \dots + A_{K-1} + A_K, B_{K+1} + B_{K+2} + \dots + 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