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 are ca sef indirect seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, val[X].
 
Exista 2 operatii:
-operatia de update: Noua valoarea asociata a 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 mai apoi va concedia toti angajatii care il au ca sef indirect pe X, cat si pe X. Antonio este curios cate shot-uri de tequila va bea Zetul **in medie**.

Exista 2 tipuri de operatii:
* 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**.

h2. Cerinta

Pentru valorile asociate initial, cat si dupa fiecare operatie de update, Antonio va cere sa aflati valoarea operatiei de query.

Pentru valorile asociate initial, cat si dupa fiecare operatie de update, Antonio va cere sa aflati raspunsul la operatia de query.

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 a lui X este Y);

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);

h2. Date de ieşire

În fişierul de ieşire $tequila.out$ va contine M + 1 linii, raspunsul pentru fiecare query.

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

h2. Restricţii si precizari

* Fie Z seful direct al angajatului X. Spunem ca seful indirect al lui X este fie Z, fie seful indirect al lui Z.

* Fie $Y$ seful direct al angajatului $X$. Spunem ca un angajat este sef indirect al lui $X$ daca acesta este fie $Y$, fie un sef indirect al lui $Y$.
 

* Dupa o operatie de query, Zetul va angaja la loc toti membrii firmei.
* Seful suprem va avea seful direct codificat cu -1.

* $1 ≤ val[X] ≤ 100000$ (1 ≤ X ≤ N)
* Rezultatul se considera corect daca **|rezultat_comisie - rezultat_participant| ≤ 10^-5^**

* $1 ≤ val{~X~} ≤ 100000$ ($1 ≤ X ≤ N$)
 
* Rezultatul afisat se considera corect daca **|rezultat_comisie - rezultat_participant| ≤ 10^-5^**

* **Subtask 1 (20 puncte)**: $1 ≤ N ≤ 20$ si nu exista update-uri
* **Subtask 2 (10 puncte)**: $1 ≤ N ≤ 100000$, nu vor exista 2 angajati cu acelasi sef direct si nu exista update-uri