Stadionul pe care Taylor Swift concertează în cadrul Turului Eras 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 ≤ i ≤ N și 1 ≤ j ≤ 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 x 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 ≤ a ≤ 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 ≤ a ≤ 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 ≤ i ≤ K) este descrisă printr-o pereche formată din două colțuri: colțul stânga-sus (xi,1 , yi,1 ) și colțul dreapta-jos (xi,2 , yi,2 ), în această ordine (1 ≤ xi,1 ≤ xi,2 ≤ N și 1 ≤ yi,1 ≤ yi,2 ≤ M). Astfel, scaunul dintr-o celulă (t, s) se află într-o submatrice i dacă xi,1 ≤ t ≤ xi,2 și yi,1 ≤ s ≤ yi,2.

Cerința

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 x K numere naturale, reprezentând, în ordine, perechile de câte două colțuri ale celor K submatrice din întrebarea descrisă, adică: x1,1, y1,1, x1,2, y1,2, …, xk,1, yk,1, xk,2, respectiv yk,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 va 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 ≤ N, M ≤ 1.000.000.000.
• 1 ≤ U ≤ 500.000 și 1 ≤ v ≤ 1000 pentru fiecare dintre cele U modificări.
• 1 ≤ Q ≤ 1000 și 1 ≤ K ≤ 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: x1,1 = 1, y1,1 = 2, x1,2 = 4, y1,2 = 3 (pentru prima submatrice: i = 1) și x2,1 = 1, y2,1 = 2, x2,2 = 2, y2,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.