== include(page="template/taskheader" task_id="inception") ==
Î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.
Î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.
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
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:
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
{**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.
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
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].
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.
* 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
