C0632 [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$，询问政府的最小开支。

样例输入 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