AT_abc479_d.Back and Forth Distance

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.

有 $N$ 个正方形从左到右依次排列，编号为 $1, 2, \ldots, N$。

当你位于第 $i$ 个正方形时，你可以执行以下两种移动之一：

• 选择一个整数 $j$，满足 $1 \leq j < i$，然后移动到第 $j$ 个正方形。该移动的代价为 $L_i$。

• 选择一个整数 $j$，满足 $i < j \leq N$，然后移动到第 $j$ 个正方形。该移动的代价为 $R_i$。

你将收到 $Q$ 个查询，需对每个查询作答。每个查询的格式如下：

• 给定整数 $s$ 和 $t$，求从第 $s$ 个正方形出发，通过若干次上述移动到达第 $t$ 个正方形所需的最小总代价。

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$

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

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

其中，$\text{query}_i$ 表示第 $i$ 个查询，其格式如下：

$s$ $t$

Output $Q$ lines.

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

输出 $Q$ 行。

第 $i$ 行应包含第 $i$ 个查询的答案。

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

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.

样例 1 解释：
我们解释第一个和第二个查询。

对于第一个查询，若直接从方格 $1$ 移动到方格 $2$，总代价为 $R_1 = 3$，这是可能的最小总代价。

对于第二个查询，若从方格 $2$ 移动到方格 $4$，再从方格 $4$ 移动到方格 $1$，总代价为 $R_2 + L_4 = 3$，这是可能的最小总代价。

约束条件

• $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$。
• 每个查询中，$s \neq t$。
• 所有输入值均为整数。