Eras

Stadionul pe care Taylor Swift concertează în cadrul $\text{Turului Eras} \textregistered$ poate fi reprezentat cu ajutorul unei matrice cu $N$ linii și $M$ coloane, numerotate începând de la $1$. În fiecare celulă $(i, j)$, de pe linia $i$ și coloana $j$ ($1 \leq i \leq N$ și $1 \leq j \leq M$), se află câte un scaun pe care pot fi așezate brățări ale prieteniei. Înainte de concert, pe fiecare dintre dintre cele $N \times M$ scaune, nu se află nicio brățară.

Pe durata concertului, Steven efectuează, în ordine, $U$ modificări, care pot fi de două tipuri:

• tipul $($L$, a, v)$ — cu semnificația că pe fiecare dintre cele $M$ scaune de pe linia $a$ sunt așezate câte $v$ brățări noi ($1 \leq a \leq N$);
• tipul $($C$, a, v)$ — cu semnificația că pe fiecare dintre cele $N$ scaune de pe coloana $a$ sunt așezate câte $v$ brățări noi ($1 \leq a \leq M$).

După ce toate modificările au fost efectuate, Caroline îi pune lui Steven, în ordine, $Q$ întrebări. Pentru fiecare întrebare, se consideră un număr natural $K$ și descrierile a $K$ submatrice. Steven trebuie să determine câte brățări sunt, în total, pe scaunele ce se află în cel puțin una dintre cele $K$ submatrice considerate.

În cadrul întrebării, fiecare submatrice $i$ ($1 \leq i \leq K$) este descrisă printr-o pereche formată din două colțuri: colțul stânga-sus $(x_{i, 1}, y_{i, 1})$ și colțul dreapta-jos $(x_{i, 2}, y_{i, 2})$, în această ordine ($1 \leq x_{i, 1} \leq x_{i, 2} \leq N$ și $1 \leq y_{i, 1} \leq y_{i, 2} \leq M$). Astfel, scaunul dintr-o celulă $(t, s)$ se află într-o submatrice $i$ dacă $x_{i, 1} \leq t \leq x_{i, 2}$ și $y_{i, 1} \leq s \leq y_{i, 2}$.

Cerință

Ajutați-l pe Steven să răspundă corect la toate cele $Q$ întrebări puse de Caroline!

Date de intrare

Pe prima linie a fișierului de intrare eras.in se află numerele naturale $N$, $M$ și $U$, în această ordine. Pe fiecare dintre următoarele $U$ linii se află, în ordine, câte un caracter (care poate fi fie L, fie C), urmat de câte două numere naturale, reprezentând descrierile celor $U$ modificări, în ordinea efectuării lor. Pe următoarea linie se află numărul natural $Q$. Pe fiecare dintre următoarele $Q$ linii se află câte un număr natural $K$, urmat de câte $4 \cdot K$ numere naturale, reprezentând, în ordine, perechile de câte două colțuri ale celor $K$ submatrice din întrebarea descrisă, adică: $x_{1, 1}$, $y_{1, 1}$, $x_{1, 2}$, $y_{1, 2}$, $\dots$, $x_{k, 1}$, $y_{k, 1}$, $x_{k, 2}$, respectiv $y_{k, 2}$. Cele $Q$ linii reprezintă, în ordine, descrierile celor $Q$ întrebări. Numerele și literele (L sau C) aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire eras.out conține $Q$ linii, pe cea de a $i$-a linie aflându-se răspunsul corect pentru cea de a $i$-a întrebare pusă de Caroline lui Steven.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000 \ 000 \ 000$
• $1 \leq U \leq 500 \ 000$ și $1 \leq v \leq 1 \ 000$ pentru fiecare dintre cele $U$ modificări
• $1 \leq Q \leq 1 \ 000$ și $1 \leq K \leq 100$ pentru fiecare dintre cele $Q$ întrebări
• Pe fiecare scaun pot fi așezate oricât de multe brățări.
• Se recomandă folosirea tipului de date long long.

Exemplul 1

eras.in

6 6 3
L 1 4
C 3 5
L 5 2
2
2 1 2 4 3 1 2 2 4
2 5 1 6 6 1 6 1 6

eras.out

32
26

Explicație

Matricea care reprezintă stadionul are $N = 6$ linii și $M = 6$ coloane. Steven efectuează $U = 3$ modificări, după cum urmează: în cadrul primei modificări, adaugă câte $v = 4$ brățări pe fiecare dintre cele șase scaune de pe prima linie, în cadrul celei de a doua modificări, adaugă câte $v = 5$ brățări pe fiecare dintre cele șase scaune de pe a treia coloană, iar în cadrul celei de a treia modificări, adaugă câte $v = 2$ brățări pe fiecare dintre cele șase scaune de pe a cincea linie.

Caroline îi pune, în ordine, $Q = 2$ întrebări lui Steven:

• În cadrul primei întrebări, se consideră descrierile a $K = 2$ submatrice: $x_{1, 1} = 1$, $y_{1, 1,} = 2$, $x_{1, 2} = 4$, $y_{1, 2} = 3$ (pentru prima submatrice: $i = 1$) și $x_{2, 1} = 1$, $y_{2, 1} = 2$, $x_{2, 2} = 2$, $y_{2, 2} = 4$ (pentru a doua submatrice: $i = 2$);
• În cadrul celei de a doua întrebări, se consideră, de asemenea, descrierile a $K = 2$ submatrice.

Exemplul 2

eras.in

5 4 4
L 2 50
C 2 4
L 3 23
C 2 3
3
1 1 1 5 4
3 1 2 1 2 2 2 5 4 1 3 5 3
1 1 3 1 4

eras.out

327
254
0

Explicație

Matricea are $N = 5$ linii și $M = 4$ coloane. Steven efectuează $U = 4$ modificări, iar Caroline îi pune $Q = 3$ întrebări.