Problem Statement

You are given an edge-weighted undirected graph with $N+1$ vertices numbered $1$ to $N+1$. For each integer $i$ satisfying $1 \leq i \leq N$, there is an edge of weight $A_i$ connecting vertex $i$ and vertex $(i \bmod N) + 1$. Also, for each integer $i$ satisfying $1 \leq i \leq N$, there is an edge of weight $B_i$ connecting vertex $i$ and vertex $N+1$. There are no other edges.

Process $Q$ queries. In each query, you are given $S$ and $T$; find the length of the shortest path from vertex $S$ to vertex $T$.

Constraints

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• $1 \leq S \lt T \leq N+1$
• All input values are integers.

Input

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

N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query $\mathrm{query}_q$ is given in the following format:

S T

Output

Output $Q$ lines. The $q$-th line should contain the answer to the $q$-th query.