Intors acasa de la ONI, Antonio se plimba prin Gradina Publica din Barlad impreuna cu cel mai bun prieten al sau, Zetul.
Antonio ii spune lui Zetul urmatoarea problema, care se va da la JBOI 2016 (informatie sigura, aflata de Antonio):

Antonio si-a imaginat o firma cu $N$ angajati, numerotati de la $1$ la $N$. Fiecare angajat al firmei are cate un sef direct (in afara de seful suprem), iar fiecare angajat are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, $val{~X~}$.

Antonio si-a imaginat o firma cu $N$ angajati, numerotati de la $1$ la $N$. Fiecare angajat al firmei are cate un sef direct (in afara de seful suprem), iar fiecare angajat il are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, $val{~X~}$.
Exista $2$ tipuri de operatii:

Exista 2 tipuri de operatii:

* Update: Noua valoarea asociata angajatului $X$ va fi $Y$;

* operatia de update: Noua valoarea asociata angajatului $X$ va fi $Y$;
 
* operatia de query: **Cat timp** seful suprem nu este concediat, Zetul alege **la intamplare** un angajat $X$ si va fi nevoit sa bea $val{~X~}$ shot-uri de tequila, iar apoi il va concedia atat pe $X$ cat si pe toti angajatii care il au ca sef indirect pe $X$. Antonio este curios cate shot-uri de tequila va bea Zetul **in medie (eng. "expected value")**.

* Query: **Cat timp** seful suprem nu este concediat, Zetul alege **la intamplare** un angajat $X$ si va fi nevoit sa bea $val{~X~}$ shot-uri de tequila, iar apoi il va concedia atat pe $X$ cat si pe toti angajatii care il au ca sef indirect pe $X$. Antonio este curios cate shot-uri de tequila va bea Zetul **in medie** (eng. "expected value").

h2. Cerinta

h2. Date de intrare

Fisierul de intrare $tequila.in$ va contine pe prima linie doua numere naturale $N$ si $M$, reprezantand numarul de angajati ai firmei si numarul de update-uri;
Urmatoarea linie va contine $N$ numere naturale - pentru fiecare angajat $X$ ({$1 ≤ X ≤ N$}) valoarea asociata initial;
Urmatoarele $N$ linii vor descrie firma, pentru fiecare angajat $X$ ({$1 ≤ X ≤ N$}) seful direct al acestuia;
Urmatoarele $M$ linii vor descrie operatiile de update sub forma: $X Y$ (noua valoare asociata lui $X$ este $Y$);

Fisierul de intrare $tequila.in$ va contine pe prima linie doua numere naturale <tex> N </tex> si <tex> M </tex>, reprezantand numarul de angajati ai firmei si, respectiv, numarul de update-uri;
Urmatoarea linie va contine <tex> N </tex> numere naturale - pentru fiecare angajat <tex> X </tex> (<tex> 1 \leq X \leq N </tex>) valoarea asociata initial, <tex> val_X </tex>;
Urmatoarele <tex> N </tex> linii vor descrie firma - pentru fiecare angajat <tex> X </tex> (<tex> 1 \leq X \leq N </tex>), seful direct al acestuia;
Urmatoarele <tex> M </tex> linii vor descrie operatiile de update sub forma: <tex> X Y </tex> (noua valoare asociata lui <tex> X </tex> este <tex> Y </tex>, echivalent cu <tex> val_X = Y </tex>);

h2. Date de ieşire

Fişierul de ieşire $tequila.out$ va contine $M + 1$ linii, reprezentand raspunsurile pentru fiecare query.

Fişierul de ieşire $tequila.out$ va contine <tex> M + 1 </tex> linii, reprezentand raspunsul pentru fiecare query in parte.

h2. Restricţii si precizari