像所有孩子一样,阿莱莎喜欢庆祝新年。在庆祝活动期间,他和他的全家装饰了枞树。和所有孩子一样,阿莱莎喜欢玩花环——由灯泡组成的链子。
Alesha 使用大小为 n × m 的网格场进行游戏。字段的行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。
Alesha 有 k 个花环,他将其放置在场地上。他这样做的方式是,每个花环的每个灯泡都位于场地中某个单元的中心,并且每个单元最多包含一个灯泡。当然,灯泡(在某些花环中是邻居)出现在相邻的单元格中。
花环放置示例。
每个花环随时关闭或打开。如果某个花环打开,则其每个灯泡都会打开,这同样适用于关闭的花环。整个花环中的每个灯泡都是独一无二的,因此,打开时,会给阿莱莎带来一些快乐,用整数值来描述。关掉灯泡不会给阿莱莎带来任何乐趣。
Alesha 可以打开和关闭花环,并想知道放置在场地某个矩形部分的单元格中心的灯泡给他带来的快乐值的总和。最初,所有花环都打开。
Alesha还很小,无法添加大数字。他非常请求你帮助他。
输入
输入的第一行包含三个整数 n、m 和 k (1 ≤ n, m, k ≤ 2000)——分别是字段行数、字段列数和放置在字段上的花环数。
下一行包含花环设置描述,格式如下:
单个花环描述的第一行包含一个整数 len (1 ≤ len ≤ 2000) — 花环中灯泡的数量。
接下来的 len 行包含三个整数 i、j 和 w(1 ≤ i ≤ n、1 ≤ j ≤ m、1 ≤ w ≤ 109)——包含灯泡的单元格的坐标以及 Alesha 在打开时从中获取的愉悦值。灯泡按照它们在花环中形成链条的顺序排列。保证相邻的灯泡放置在一侧相邻的单元中。
下一行包含单个整数 q (1 ≤ q ≤ 106) — Alesha 游戏中的事件数。接下来的 q 行按时间顺序描述事件。其中第 i 个采用以下格式之一描述第 i 个事件:
- 开关 i — 如果第 i 个花环已打开,Alesha 将其关闭;如果第 i 个花环已关闭,则将其打开。保证1 ≤ i ≤ k。
- ASK x1 y1 x2 y2 — Alesha 想知道放置在场地矩形部分中的灯泡的愉悦值总和。零件的左上角单元格具有坐标 (x1, y1),右下单元格具有坐标 (x2, y2)。保证1 ≤ x1 ≤ x2 ≤ n和1 ≤ y1 ≤ y2 ≤ m。输入中此类事件不超过 2000 个。
输入中的所有数字均为整数。
请注意,输入量较大,使用某些输入方式时请小心。特别是,不建议在 C++ 代码中使用 cin,以及在 Java 代码中使用 class Scanner。
输出
对于每个 ASK 操作,在单独的行中打印 Alesha 想要知道的总和。按时间顺序打印答案。
示例
输入 #1
4 4 3 5 1 1 2 1 2 3 2 2 1 2 1 4 3 1 7 4 1 3 1 2 3 3 2 4 3 1 4 1 7 4 1 1 4 2 9 3 2 8 3 3 3 4 3 4 4 4 1 3 4 1 2 ASK 2 2 3 3 ASK 1 1 4 4
输出 #1
15 52
输入 #2
4 4 1 8 4 1 1 3 1 2 2 1 1 1 1 7 1 2 5 2 2 4 2 3 1 1 3 1 3 ASK 1 1 3 2 SWITCH 1 ASK 1 1 3 2
输出 #2
19 0
注意
此图展示了第一个示例案例。