inception

Inception

== 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.
h2. Cerinţă

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