Garlands

题意翻译

### 题目大意 Alesha 喜欢玩灯条,灯条指由若干个灯泡组成的链。 Alesha 使用由 $n\times m$ 个单元格组成的网格来玩灯条,网格的行从上到下从 $1$ 到 $n$ 编号,列从左到右从 $1$ 到 $m$ 编号。 Alesha 有 $k$ 根灯条,这些灯条都被放在了网格上,同一根灯条内,相邻的两个灯泡在网格中都是相邻的。网格的每个单元格中最多只有一个灯泡。每个灯泡亮着的时候都有一个快乐值,熄灭的灯泡都没有快乐值。 最开始,所有灯泡都是亮着的。Alesha 进行若干次以下两种操作: 1. 选择一个灯条,如果这个灯条上的灯泡是亮着的,把灯条上的所有灯泡都熄灭;如果这个灯条上的灯泡是熄灭的,把灯条上的所有灯泡都点亮 2. 选择网格的一个子矩阵,求这个子矩阵中的所有亮着的灯泡的快乐值之和。**保证这种操作最多出现 $2000$ 次。**

题目描述

Like all children, Alesha loves New Year celebration. During the celebration he and his whole family dress up the fir-tree. Like all children, Alesha likes to play with garlands — chains consisting of a lightbulbs. Alesha uses a grid field sized $ n×m $ for playing. The rows of the field are numbered from $ 1 $ to $ n $ from the top to the bottom and columns are numbered from $ 1 $ to $ m $ from the left to the right. Alesha has $ k $ garlands which he places at the field. He does so in the way such that each lightbulb of each garland lies in the center of some cell in the field, and each cell contains at most one lightbulb. Of course lightbulbs, which are neighbours in some garland, appears in cells neighbouring by a side. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF707E/3d944d29acd479b81853444b6813c350313a6711.png) The example of garland placing. Each garland is turned off or turned on at any moment. If some garland is turned on then each of its lightbulbs is turned on, the same applies for garland turned off. Each lightbulb in the whole garland set is unique, and thus, being turned on, brings Alesha some pleasure, described by an integer value. Turned off lightbulbs don't bring Alesha any pleasure. Alesha can turn garlands on and off and wants to know the sum of pleasure value which the lightbulbs, placed in the centers of the cells in some rectangular part of the field, bring him. Initially all the garlands are turned on. Alesha is still very little and can't add big numbers. He extremely asks you to help him.

输入输出格式

输入格式


The first line of the input contains three integers $ n $ , $ m $ and $ k $ ( $ 1<=n,m,k<=2000 $ ) — the number of field rows, the number of field columns and the number of garlands placed at the field respectively. Next lines contains garlands set description in the following format: The first line of a single garland description contains a single integer $ len $ ( $ 1<=len<=2000 $ ) — the number of lightbulbs in the garland. Each of the next $ len $ lines contains three integers $ i $ , $ j $ and $ w $ ( $ 1<=i<=n $ , $ 1<=j<=m $ , $ 1<=w<=10^{9} $ ) — the coordinates of the cell containing a lightbullb and pleasure value Alesha gets from it if it is turned on. The lightbulbs are given in the order they are forming a chain in the garland. It is guaranteed that neighbouring lightbulbs are placed in the cells neighbouring by a side. The next line contains single integer $ q $ ( $ 1<=q<=10^{6} $ ) — the number of events in Alesha's game. The next $ q $ lines describes events in chronological order. The $ i $ -th of them describes the $ i $ -th event in the one of the following formats: - SWITCH $ i $ — Alesha turns off $ i $ -th garland if it is turned on, or turns it on if it is turned off. It is guaranteed that $ 1<=i<=k $ . - ASK $ x_{1} $ $ y_{1} $ $ x_{2} $ $ y_{2} $ — Alesha wants to know the sum of pleasure values the lightbulbs, placed in a rectangular part of the field. Top-left cell of a part has coordinates $ (x_{1},y_{1}) $ and right-bottom cell has coordinates $ (x_{2},y_{2}) $ . It is guaranteed that $ 1<=x_{1}<=x_{2}<=n $ and $ 1<=y_{1}<=y_{2}<=m $ . There is no more than $ 2000 $ events of this type in the input. All the numbers in the input are integers. Please note that the input is quite large, so be careful while using some input ways. In particular, it's not recommended to use cin in codes on C++ and class Scanner in codes on Java.

输出格式


For each ASK operation print the sum Alesha wants to know in a separate line. Print the answers in chronological order.

输入输出样例

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

说明

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF707E/59774fd8bd70ea840f4a3c4bb4b95e2f490588f0.png) This image illustrates the first sample case.