== include(page="template/taskheader" task_id="inception") ==
Poveste şi cerinţă...
În seara dinaintea probei de concurs, Cobby a avut un vis demn de un Oscar, cu mai multe evenimente. Se făcea că lumea era reprezentată ca o matrice pătratică de latură {**N**}, cu liniile şi coloanele numerotate de la {**1**} la {**N**}, în care fiecare element era iniţial vid. Privind în jur, a realizat că atunci când visează un element al matricei, situat la intersecţia liniei {**i**} cu coloana {**j**}, interiorul acestuia se împarte în {**N**} linii şi {**N**} coloane, ca o nouă matrice. Apoi, dacă visează la un element din matricea nou formată sau din cea iniţială, se întâmplă la fel.
Pentru a nu se rătăci, eroul nopţii a decis să atribuie un indice fiecărei matrice formată începând cu cea iniţială căreia i-a asociat indicele {**1**}. Matricele care se creează primesc indici numere naturale consecutive (2, 3, ...), în ordinea în care se obţin. Astfel, fiecare element din visul lui Cobby este definit de 3 numere: {**id**} - indicele atribuit matricei din care face parte, {**i**} şi {**j**} - indicii liniei şi coloanei pe care se află elementul.
Cobby realizează că, oricât ar încerca, nu poate visa un element decât o singură dată. Pentru a face visul şi mai interesant, el reţine pentru fiecare matrice un număr natural denumit “coeficient de importanţă”, iniţial {**0**} pentru fiecare matrice din vis. Din când în când, eroul nostru alege una dintre matrice şi adaugă o valoare {**VAL**} la coeficientul de importanţă al ultimelor {**NR**} matrice din care s-a obţinut aceasta, inclusiv ea.
h2. Cerinţă
După ce au loc toate evenimentele din vis, Cobby vrea să ştie valoarea finală a coeficientului de importanţă pentru un şir de {**K**} matrice date prin indicii lor. Deoarece el se grăbeşte să participe la Concursul Naţional Urmaşii lui Moisil, îţi revine ţie misiunea de a găsi răspunsul pentru fiecare matrice.
h2. Date de intrare
Fişierul de intrare $inception.in$ ...
Pe prima linie a fişierului $inception.in$ se află valorile {**N**} - numărul de linii şi coloane din fiecare matrice, {**Q**} - numărul de evenimente care au loc în visul lui Cobby, {**K**} - numărul de matrice pentru care Cobby vrea să ştie coeficientul de importanţă. Următoarele {**Q**} linii respectă unul dintre formatele:
{**1 id i j**} - Cobby visează elementul de pe linia {**i**} şi coloana {**j**} din matricea cu indicele {**id**}
{**2 id NR VAL**} - Cobby adaugă valoarea {**VAL**} la coeficienţii de importanţă a {**NR**} matrice începând cu matricea cu indicele {**id**}
Pe linia {**Q + 2**} se află {**K**} valori {**id1 id2 … idK**}, separate prin câte un spaţiu, ce reprezintă indicii matricelor pentru care trebuie afişată valoarea finală a coeficientului de importanţă. Evenimentele se petrec în ordinea în care sunt date în fişier.
h2. Date de ieşire
În fişierul de ieşire $inception.out$ ...
Pe prima linie a fişierului $inception.out$ se află {**K**} valori {**r1 r2...rK**}, separate prin câte un spaţiu, unde {**ri**} reprezintă coeficientul final al matricei cu id-ul {**idi, i ∈ [1,K].**}
h2. Restricţii
* $... ≤ ... ≤ ...$
* 1 ≤ {**N**} ≤ 500000
* 1 ≤ {**Q**} ≤ 300000
* 1 ≤ {**VAL**} ≤ 1000
* 1 ≤ {**K, NR, id**} ≤ numărul total de operaţii de tipul {**1**}.
* În ambele tipuri de evenimente valoare {**id**} corespunde unei matrice formate anterior.
* Se garantează că există cel puţin {**NR**} matrice care pot fi modificate pentru operaţia de tipul {**2**}.
* Pentru {**20%**} dintre teste orice matrice va conţine cel mult un element visat.
h2. Exemplu
table(example). |_. inception.in |_. inception.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3 6 3
1 1 2 3
1 2 3 3
2 3 3 5
1 1 3 1
1 2 3 1
2 5 2 3
2 1 4
| 8 5 0
|
h3. Explicaţie
...
{! problema/inception?inception.jpg 35% !}
== include(page="template/taskfooter" task_id="inception") ==
