Problem Statement

There are $N$ squares arranged in a row, numbered $1, 2, \ldots, N$ from left to right.

When you are on square $i$, you can make one of the following moves.

• Choose an integer $j$ such that $1 \leq j < i$, and move to square $j$. The cost of this move is $L_i$.
• Choose an integer $j$ such that $i < j \leq N$, and move to square $j$. The cost of this move is $R_i$.

You are given $Q$ queries. Answer each of them. Each query is in the following format.

• Integers $s$ and $t$ are given. Find the minimum total cost required to reach square $t$ from square $s$ by repeatedly making moves.

Constraints

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 3 \times 10^5$
• $1 \leq L_i \leq 10^9$ $(2 \leq i \leq N)$
• $1 \leq R_i \leq 10^9$ $(1 \leq i \leq N - 1)$
• $1 \leq s, t \leq N$ for each query.
• $s \neq t$ for each query.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$ $Q$
• $L_2$ $L_3$ $\ldots$ $L_N$
• $R_1$ $R_2$ $\ldots$ $R_{N - 1}$
• $\text{query}_1$
• $\text{query}_2$
• $\vdots$
• $\text{query}_Q$

Here, $\text{query}_i$ is the $i$-th query, given in the following format:

• $s$ $t$

Output

Output $Q$ lines.

The $i$-th line should contain the answer to the $i$-th query.

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

3
3
1
5
3
2
9

We explain the first and second queries.

For the first query, if you move directly from square $1$ to square $2$, the total cost is $R_1 = 3$, which is the minimum possible total cost.

For the second query, if you move from square $2$ to square $4$ and then from square $4$ to square $1$, the total cost is $R_2 + L_4 = 3$, which is the minimum possible total cost.

• Source: AtCoder ABC 479 D