题目描述

给定一个包含 $N+1$ 个顶点的带权无向图，顶点编号为 $1$ 到 $N+1$。

对于每个满足 $1 \leq i \leq N$ 的整数 $i$，存在一条权值为 $A_i$ 的边连接顶点 $i$ 与顶点 $(i \bmod N) + 1$。

此外，对于每个满足 $1 \leq i \leq N$ 的整数 $i$，存在一条权值为 $B_i$ 的边连接顶点 $i$ 与顶点 $N+1$。不存在其他边。

处理 $Q$ 个询问。每个询问给定 $S$ 与 $T$，求从顶点 $S$ 到顶点 $T$ 的最短路径长度。

输入格式

输入按以下格式从标准输入读入：

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

这里，$\mathrm{query}_q$ 表示第 $q$ 个询问，其格式如下：

• $S$ $T$

输出格式

输出 $Q$ 行。第 $q$ 行应输出第 $q$ 个询问的答案。

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

6
5
6

对于第一个询问，从顶点 $2$ 到顶点 $5$ 的一条最短路径是 $2\to1\to5$，其长度为 $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

数据范围

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

• 所有输入值均为整数。

• 来源：AtCoder ABC 477 E

子任务设置

• 子任务 1（30 分）：$N, Q \le 2000$。
• 子任务 2（30 分）：$N \le 2\times10^5$ 且 $Q \le 2000$。
• 子任务 3（40 分）：无特殊限制。