| Codeforces Round 368 (Div. 2) |
|---|
| Закончено |
Как и все дети, Алеша обожает Новый Год. В канун этого праздника он со всей семьей наряжает ёлку. Как и все дети, Алеша любит играть с гирляндами — цепочками, состоящими из лампочек.
Для игры Алеша использует клеточное поле размера n × m. Строки поля пронумерованы сверху вниз от 1 до n, а столбцы — слева направо от 1 до m.
У Алеши есть k гирлянд, которые он раскладывает на поле. Он делает это таким образом, что каждая лампочка каждой гирлянды попадает в центр некоторой клетки поля, причем в каждой клетке оказывается не более одной лампочки. Конечно же, лампочки, соседствующие в гирлянде, оказываются в соседних по стороне клетках.
Пример размещения гирлянды.
Каждая гирлянда в любой момент может быть либо включена, либо выключена. Если включена гирлянда, то включены все ее лампочки, и наоборот. Каждая лампочка в наборе гирлянд уникальна, и поэтому, будучи включенной, приносит Алеше определенное удовольствие, характеризующееся целым числом. Выключенные лампочки не приносят Алеше удовольствия.
Алеша умеет включать и выключать разложенные гирлянды и хочет узнавать сумму удовольствия, которое приносят ему лампочки, находящиеся в центрах клеток в некоторой прямоугольной области поля. Изначально все гирлянды включены.
Алеша еще совсем маленький и пока не умеет складывать большие числа. Он очень просит вас помочь ему с этим.
В первой строке содержится три целых числа 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) — координаты клетки, содержащей очередную лампочку, и удовольствие, которое Алеша получает от этой лампочки, если она включена. Лампочки перечислены в том порядке, в котором они соединены в цепочку в гирлянде. Гарантируется, что соседние лампочки находятся в соседних по стороне клетках. 
В следующей строке содержится целое число q (1 ≤ q ≤ 106) — количество событий в игре Алеши. Следующие q строк описывают события в хронологическом порядке. В i-й из них содержится описание i-го события в одном из следующих форматов:
- SWITCH i — Алеша выключает i-ю гирлянду, если она была включена, или включает, если та была выключена. Гарантируется, что 1 ≤ i ≤ k.
- ASK x1 y1 x2 y2 — Алешу интересует сумма удовольствия, которое приносят ему лампочки, находящиеся в прямоугольной области, верхняя левая клетка которой имеет координаты (x1, y1), а правая нижняя — (x2, y2). Гарантируется, что 1 ≤ x1 ≤ x2 ≤ n и 1 ≤ y1 ≤ y2 ≤ m. Во входных данных присутствует не более 2000 событий этого типа.
Все числа во входных данных целые.
Обратите внимание, что входные данные довольно объемны, поэтому будьте внимательны, используя те или иные средства ввода. В частности, в программах на языке C++ не следует использовать cin, а в программах на языке Java — класс Scanner.
Для каждой операции ASK в отдельной строке выведите интересующую Алешу сумму удовольствий. Ответы выводите в хронологическом порядке.
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
15
52
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
19
0
Иллюстрация к первому примеру из условия.
