Inna非常喜欢甜食。这就是为什么她想和迪玛和塞雷贾一起玩“甜蜜矩阵”游戏。但塞雷贾是个大人物,所以这场比赛对他来说意义不大。 Sereja 建议玩“大甜蜜矩阵”游戏。
“Large Sweet Matrix” 游戏场是一个 n × m 矩阵。让我们将矩阵的行从 1 到 n 编号,将列从 1 到 m 编号。我们将第 i 行第 j 列中的单元格表示为 (i, j)。矩阵的每个单元格可以包含多个糖果,最初所有单元格都是空的。游戏分 w 步进行,每一步都会发生以下两个事件之一:
1. Sereja 选择 5 个整数 x1, y1, x2, y2, v (x1 ≤ x2, y1 ≤ y2) 并向每个矩阵单元 (i, j) 添加 v 颗糖果(x1 ≤ i ≤ x2;y1 ≤ j ≤ y2)。
2. Sereja 选择四个整数 x1, y1, x2, y2 (x1 ≤ x2, y1 ≤ y2)。然后他要求 Dima 计算单元格 (i, j) (x1 ≤ i ≤ x2; y1 ≤ j ≤ y2) 中的糖果总数,并要求 Inna 计算矩阵 (p, q) 单元格中的糖果总数,满足以下逻辑标准: (p < x1 OR p > x2) AND (q < y1 或 q > y2)。最后,Sereja 要求写下 Dima 计算出的数字与 Inna 计算出的数字之间的差值 (D - I)。
不幸的是,Sereja 的矩阵实在是太大了。这就是为什么伊娜和迪玛无法应对算计的原因。帮助他们!
输入
输入的第一行包含三个整数 n、m 和 w (3 ≤ n, m ≤ 4·106; 1 ≤ w ≤ 105)。
接下来的 w 行描述了游戏中的动作。
- 描述第一类型事件的行包含 6 个整数:0、x1、y1、x2、y2 和 v (1 ≤ x1 ≤ x2 ≤ n;1 ≤ y1 ≤ y2 ≤ m;1 ≤ v ≤ 109)。
- 描述第二类型事件的行包含 5 个整数:1、x1、y1、x2、y2 (2 ≤ x1 ≤ x2 ≤ n - 1;2 ≤ y1 ≤ y2 ≤ m - 1)。
保证第二种类型的移动至少发生一次。保证单次操作添加的糖果不会超过109颗。
注意,约束非常大,所以请使用最优的数据结构。最大测试将在预测试中进行。
输出
对于每第二个类型 move,在一行上打印一个整数 - Dima 和 Inna 的数字之间的差异。
示例
输入 #1
4 5 5 0 1 1 2 3 2 0 2 2 3 3 3 0 1 5 4 5 1 1 2 3 3 4 1 3 4 3 4
输出 #1
2 -21
注意
示例注释。第一次查询后,矩阵如下所示:
第二个之后是:
第三个之后是:
对于第四个查询,Dima 的总和等于 5 + 0 + 3 + 0 = 8,Inna 的总和等于 4 + 1 + 0 + 1 = 6。查询的答案等于 8 - 6 = 2。对于第五个查询,Dima 的总和等于 0,Inna 的总和等于 18 + 2 + 0 + 1 = 21。答案查询结果为 0 - 21 = -21。