AT_abc477_e.Wheel Distance

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$.

给你一个带边权的无向图，该图共有 $N+1$ 个顶点，编号为 $1$ 到 $N+1$。
对每个满足 $1 \leq i \leq N$ 的整数 $i$，存在一条连接顶点 $i$ 与顶点 $(i \bmod N) + 1$、权重为 $A_i$ 的边。
此外，对每个满足 $1 \leq i \leq N$ 的整数 $i$，存在一条连接顶点 $i$ 与顶点 $N+1$、权重为 $B_i$ 的边。图中不存在其他边。

你需要处理 $Q$ 个查询。在每个查询中，给定起点 $S$ 和终点 $T$，请计算从顶点 $S$ 到顶点 $T$ 的最短路径长度。

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$

输入从标准输入中按以下格式给出：

$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$

每个查询 $\mathrm{query}_q$ 按以下格式给出：

$S$ $T$

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

输出 $Q$ 行。第 $q$ 行应包含第 $q$ 个查询的答案。

Sample 1 Explanation:
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$.

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.

样例 1 解释：
对于第一个查询，从顶点 $2$ 到顶点 $5$ 的一条最短路径为 $2\to1\to5$，其长度为 $A_1+A_5=1+5=6$。

约束条件

• $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$
• 所有输入值均为整数。