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.
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