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.