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

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

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

Exista 2 operatii:

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

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

Cerinta:

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

Urmatoarele M linii vor descrie operatiile de update, si vor fi de forma: X Y (val[X] = Y);

h2. Date de ieşire