划分矿区

湖泊的尽头是一片矿区——不是普通的矿区，是由无数数据块堆成的矩阵。每个数据块有一个能量值，Zero会不定期给某一行或某一列的所有块同时增加或减少能量。

"要实时知道任意一个子矩阵的总能量。"Echo说，"如果每次修改都逐个块更新，太慢了。"

"分块浇水。"你说，"把整个矩阵切成很多小段，每次浇水（修改）时，如果整段都在范围内，就直接在段头上做个标记；如果只有一部分在范围内，就逐个块更新。查询的时候，把段头上的标记累加进每个块的实际值。"

"就像……"CC想了想，"给花浇水。整片花圃直接开喷头，边角的花盆单独浇。"

"对。"

你开始写。把矩阵的每一行切成很多小段，每段维护一个累加标记。修改一行的一段区间时，如果整段被覆盖，就打标记；否则逐个更新。查询子矩阵时，把每行在区间内的段加起来，同时把段头上的标记算进去。

屏幕上跳出了结果。第47号数据块的总能量突然从12变成了47。

"又是47。"CC说。

"第47号块。"Echo说，"那是Zero的能量核心。它在往那里注入能量。"

"那我们怎么办？"

"吸干它。"CC说，"把它周围的能量都吸走，让它孤立。"

Echo看了CC一眼，投影的颜色变深了一瞬："你变狠了。"

"跟你学的。"

题目描述

$n \times m$ 的矩阵，支持子矩阵加和子矩阵和查询。

输入格式

$n, m, q$。然后 $q$ 个操作，每个操作是子矩阵加或子矩阵和查询。

输出格式

每个查询输出子矩阵和。

输入样例

5 3
1 2 3 4 5
Q 1 5
C 1 3 2
Q 1 5

输出样例

15
21

提示

• 分块。每行分块，块大小约 $\sqrt{m}$。
• 每块维护一个累加标记。
• 修改时，完整块打标记，不完整块逐个更新。
• 查询时，累加标记和实际值。

矿区深处是一片磁场——不是物理的磁场，是Zero的影响力场。每个节点有一个坐标和权值，节点之间的连线代表影响力传播的路径。Echo说，要找到一个节点，使得所有其他节点到它的影响力之和最小。

"那就是磁场的心脏。"Echo说，"影响力最小的点，就是Zero最脆弱的地方。"

"咋个找？"CC问，"一个个试？"

"节点太多，一个个试太慢。"你说，"先找一个大概的中心——把所有节点的坐标平均一下，得到一个近似的心脏位置。然后在它附近的一小片区域里，逐个精算。"

"这像……"CC想了想，"先用大网捞信号，再在网里挑最大的？"

"对。"