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$ $\ldots$ $A_N$
• $B_1$ $B_2$ $\ldots$ $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.

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

6
5
6

• For the first query, one shortest path from vertex $2$ to vertex $5$ is $2\to1\to5$, and its length is $A_1+A_5=1+5=6$.

10 12
95786828 55052989 7398452 90695030 73248844 120697567 77915140 68865651 15301338 68674005
690874817 21524935 244587369 529970100 736247510 757265588 993115119 576136368 21553212 219853538
5 6
5 8
2 6
3 7
1 3
3 4
8 11
1 10
2 6
6 8
8 9
5 8

73248844
265090269
226395315
244911927
150839817
7398452
90418863
68674005
226395315
198612707
68865651
265090269

• Source: AtCoder ABC 477 E