== include(page="template/taskheader" task_id="aparate") ==
Poveste şi cerinţă...
_În timp ce lumea e în carantină, $K0Kalaru 47$ se întoarce în habitatul său (adică aici, la Junior Challenge). Nature is healing._
De când nu l-am mai văzut, acesta a trecut prin foarte multe peripeţii. După ce a câştigat bani de la ediţiile trecute de JBOI, primul lucru pe care l-a făcut a fost să joace la jocurile de noroc (şi i-a pierdut pe toţi). În timp ce el vă povesteşte cu exactitate ce a jucat, el vă provoacă să calculaţi chiar voi ce pierderi imense a avut acesta.
La început, el vă descrie aparatul la care a jucat. Acesta este o matrice cu $N$ linii (numerotate de la 1 la $N$) şi $M$ coloane (numerotate de la 1 la $M$) cu valori întregi. $K0Kalaru 47$ începe să vă povestească $Q$ evenimente în ordine cronologică. Evenimentele sunt de următoarea formă:
* $"Loveşte violent butonul din mijloc (sau ecranul, sau aparatul, sau ce vrei)"$ - o sa îi zicem $update$ - şi coloanele cu indicii $l, l + 1, l + 2, ..., r$ se rotesc cu $k$ valori în sus.
* $"Te umpli de nervi, deoarece 'ai avut ghinion' şi ai pierdut mult mai mult decât trebuia să pierzi"$ - o să îi zicem $query$ - se luminează celulele de la coordonatele $(k, l), (k, l + 1), (k, l + 2), ..., (k, r)$, şi pierzi o sumă de bani egală cu suma celulelor aprinse. **Celulele nu rămân aprinse până la sfârşitul jocului. După această operaţie, acestea se sting la loc**.
Ca să îi demonstrezi lui $K0Kalaru 47$ că ai fost atent la toată povestea lui, vrei să îi zici la fiecare operaţie de tip $query$ câţi bani a pierdut.
h2. Date de intrare
Fişierul de intrare $aparate.in$ ...
În fişierul de intrare $aparate.in$, pe prima linie se află numerele $N, M$ şi $Q$ cu semnificaţia din enunţ.
Pe următoarele $N$ linii se află câte $M$ numere reprezentând matricea iniţială.
Pe următoarele $Q$ linii se vor afla 4 numere $tip l r k$ separate prin câte un spaţiu ce semnifică câte un eveniment:
* Dacă $tip$ este 1, atunci evenimentul respectiv este un $update$ şi coloanele cu indicii de la $l$ până la $r$ se rotesc în sus cu $k$ valori în sus
* Dacă $tip$ este 2, atunci evenimentul respectiv este un $query$ la care trebuie să raspundeţi cu suma elementelor de pe linia $k$ si coloanele cu indicii de la $l$ până la $r$
h2. Date de ieşire
În fişierul de ieşire $aparate.out$ ...
În fişierul de ieşire $aparate.out$ se vor afla pe mai multe linii răspunsurile în ordine la toate operaţiile de $query$ ale lui $K0Kalaru 47$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N$
* $2 ≤ M$
* $N * M ≤ 100.000$
* $Q ≤ 50.000$
* $1 ≤ l ≤ r ≤ M$ pentru fiecare eveniment
* $1 ≤ k ≤ N$ pentru fiecare eveniment
* $1 ≤ type ≤ 2$ pentru fiecare eveniment
* Elementele din matrice sunt valori de la $1$ până la $1.000.000$. A se observa că, deoarece valorile sunt pozitive, $K0Kalaru 47$ nu are pierderi 'negative', deci nu are cum să câştige vreodată bani.
* Fie ${@ A[1][c], A[2][c], ..., A[N][c]@}$ elementele de pe coloana $c$. O rotaţie 'în sus' a coloanei respective cu o poziţie înseamnă că se elimină elementul ${@ A[1][N], @}$ toate celălalte elemente se mută în sus cu o poziţie, iar poziţia care se eliberează jos de tot va fi înlocuită cu elementul care a fost eliminat. Astfel elementele coloanei o să fie (în ordine de sus în jos) ${@ A[2][c], A[3][c], ..., A[N][c], A[1][c]. @}$
* O rotaţie în sus cu $k$ poziţii a unei coloane înseamnă că rotim coloana respectivă cu o pozitie în sus de $k$ ori.
* $K0Kalaru 47$ nu recomandă absolut nimănui experienţa sa.
h2. Subtaskuri
* $**Subtaskul 1 (10 puncte, testele 1-2):**$ $Q ≤ 1.000$
* $**Subtaskul 2 (20 puncte, testele 3-6):**$ $M ≤ 1.000$
* $**Subtaskul 3 (30 puncte, testele 7-12):**$ $N = 2$
* $**Subtaskul 4 (40 puncte, testele 13-20):**$ Restricţiile iniţiale
h2. Exemplu
table(example). |_. aparate.in |_. aparate.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 6 5
1 3 5 2 6 7
3 4 9 2 1 9
1 1 1 1 1 1
9 9 7 7 7 9
1 3 5 2
1 2 5 3
2 4 6 1
2 3 5 2
2 1 6 3
| 10
3
27
|
h3. Explicaţie
...
Iniţial, matricea arată astfel:
$1 3 5 2 6 7$
$3 4 9 2 1 9$
$1 1 1 1 1 1$
$9 9 7 7 7 9$
După prima operaţie, ea va arăta astfel:
$1 3 **1 1 1** 7$
$3 4 **7 7 7** 9$
$1 1 **5 2 6** 1$
$9 9 **9 2 1** 9$
După a doua operaţie, ea va arăta astfel:
$1 **9 9 2 1** 7$
$3 **3 1 1 1** 9$
$1 **4 7 7 7** 1$
$9 **1 5 2 6** 9$
Răspunsul la a treia operaţie va fi $2 + 1 + 7 = 10$.
Răspunsul la a patra operaţie va fi $1 + 1 + 1 = 3$.
Răspunsul la a cincea operaţie va fi $1 + 4 + 7 + 7 + 7 + 1 = 27$.
== include(page="template/taskfooter" task_id="aparate") ==
