[SDOI2015]道路修建

题目描述

某国有 $2N$ 个城市，这 $2N$ 个城市构成了一个 $2$ 行 $N$ 列的方格网。现在该国政府有一个旅游发展计划，这个计划需要选定 $L$、$R$ 两列 $(L \leq R)$，修建若干条专用道路，使得这两列之间（包括这两列）的所有 $2(R-L+1)$ 个城市中每个城市可以只通过专用道路就可以到达这 $2(R-L+1)$ 个城市中的任何一个城市。这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建，且修建需要花费一定的费用。

由于该国政府决定尽量缩减开支，因此政府决定，选定 $L$、$R$ 后，只修建 $2(R-L+1)-1$ 条专用道路，使得这些专用道路构成一个树结构。现在你需要帮助该国政府写一个程序，完成这个任务。具体地，该任务包含 $M$ 个操作，每个操作的格式如下：

1. C x0 y0 x1 y1 w：由于重新对第 $x_0$ 行第 $y_0$ 列的城市和第 $x_1$ 行第 $y_1$ 列的城市之间的情况进行了考察，它们之间修建一条专用道路的花费变成了 $w$；
2. Q L R：若政府选定的两列分别为 $L$、$R$，询问政府的最小开支。

输入格式

第一行，两个整数 $N$、$M$。

第二行，$N-1$ 个整数，其中第 $i$ 个整数表示初始时第 $1$ 行第 $i$ 列的城市和第 $1$ 行第 $i+1$ 列的城市之间修建一条专用道路的费用。

第三行，$N-1$ 个整数，其中第 $i$ 个整数表示初始时第 $2$ 行第 $i$ 列的城市和第 $2$ 行第 $i+1$ 列的城市之间修建一条专用道路的费用。

第四行，$N$ 个整数，其中第 $i$个整数表示初始时第 $1$ 行第 $i$ 列的城市和第 $2$ 行第 $i$ 列的城市之间修建一条专用道路的费用。 接下来的 $M$ 行，每行一个操作。

输出格式

对于每个询问操作，输出一行，表示你计算出的政府的最小开支。

样例 #1

样例输入 #1

3 3
1 2
2 1
3 1 2
Q 1 3
C 1 2 2 2 3
Q 2 3

样例输出 #1

7
5

提示

对于全部的数据，$1 \leq N, M \leq 60000$，任何时刻任何一条专用道路的修建费用不超过 $10^4$。