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 seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, val[X].
 

Se da un arbore(cu radacina) cu N noduri, fiecare nod X avand o valoare asociata, val[X].

Exista 2 operatii:

-operatia de update: Noua valoarea 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**.

-operatia de update: Noua valoarea a nodului X va fi Y;
-operatia de query: Cat timp radacina nu este stearsa, Zetul alege **la intamplare** un nod X si va fi nevoit sa bea val[X] shot-uri de tequila, iar mai apoi va sterge subarborele nodului X (inclusiv nodul X). Antonio este curios cate shot-uri de tequila va bea Zetul **in medie**.
 

h2. Cerinta
Pentru arborele initial, cat si dupa fiecare operatie de update, Antonio va cere sa aflati valoarea operatiei 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 nod 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 noduri ale arborelui si numarul de update-uri;
Urmatoarea linie va contine N numere naturale, pentru fiecare nod X (1 ≤ X ≤ N) valoarea asociata initial;
Urmatoarele N linii vor descrie arborele, pentru fiecare nod X (1 ≤ X ≤ N) tatal acestuia;
Urmatoarele M linii vor descrie operatiile de update, si vor fi de forma: X Y (val[X] = Y);

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

h2. Restricţii si precizari

h2. Restricţii

* Fie Z seful direct al angajatului X. Spunem ca seful indirect al lui X este fie Z, fie seful indirect al lui Z.
* Seful suprem va avea seful direct codificat cu -1.

* Radacina va avea tatal -1.

* $1 ≤ val[X] ≤ 100000$ (1 ≤ X ≤ N)
* Rezultatul se va verifica cu o precizie de 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 noduri X si Z cu acelasi numar de sefi indirecti si nu exista update-uri
* **Subtask 3 (10 puncte)**: $1 ≤ N ≤ 100000$ si nu vor exista 2 noduri X si Z cu acelasi numar de sefi indirecti

* **Subtask 2 (10 puncte)**: $1 ≤ N ≤ 100000$, arborele este lant si nu exista update-uri
* **Subtask 3 (10 puncte)**: $1 ≤ N ≤ 100000$ si arborele este lant

* **Subtask 4 (60 puncte)**: $1 ≤ N ≤ 100000$