Rafaela

Prinţesa cu ochii verzi din regatul arborilor, Rafaela, trebuie să recupereze taxele de la toţi cetăţenii regatului. Astfel, formal, se dă un arbore cu N noduri, în fiecare nod aflându-se iniţial un număr dat de cetăţeni. Rafaela ar dori să plaseze capitala regatului într-unul dintre noduri, însă datorită fluctuaţiei numărului de cetăţeni din regat, a întâmpinat o problemă pe care ar dori să o rezolve pe calculator. Astfel, ea va efectua anumite operaţii asupra arborelui pentru a lua, în final, o decizie. Operaţiile sunt de tipul update/query şi sunt descrise mai jos:

• U nr id – caracterul $U$ urmat de două numere întregi, care reprezintă o operaţie de update şi are semnificaţia: în nodul cu indicele $id$ apare un numar de $nr$ cetăţeni (în caz că numărul este pozitiv), sau dispare un număr de $nr$ cetăţeni (în cazul în care numărul este negativ);
• Q id – caracterul $Q$ urmat de un număr întreg, reprezentând o operaţie de tip query la care voi trebuie sărăspundeţi: dacă am stabili capitala regatului în nodul cu indicele $id$, atunci care ar fi muchia cea mai des utilizată (pe care se plimbă cei mai mulţi cetăţeni) dacă toţi cetăţenii ar decide să meargă din nodurile în care se află spre capitală? Cum pot exista mai multe astfel de muchii, Rafaela se mulţumeşte doar să aflaţi numărul de cetăţeni care merg pe una dintre muchiile cele mai utilizate.

Cerinţă

Dându-se un arbore cu $N$ noduri, numărul iniţial de cetăţeni din fiecare nod şi $Q$ operaţii de tipul update/query, trebuie să răspundeţi la operaţiile de tip query.

Date de intrare

Fişierul de intrare rafaela.in conţine pe prima linie două numere naturale $N$ si $Q$, separate printr-un spaţiu, reprezentând numărul de noduri ale arborelui, respectiv numărul de operaţii efectuate. Pe următoarele $N-1$ linii se află perechi de câte două numere naturale $a$ şi $b$, separate printr-un spaţiu, reprezentând o muchie
($a$ și $b$ reprezintă două noduri din arbore). Pe următoarea linie se află $N$ numere naturale separate prin câte un spaţiu, numărul de pe poziţia $i$ reprezentând numărul de cetăţeni care se află iniţial în nodul $i$. Pe următoarele $Q$ linii se află operaţii de tip update/query, o operaţie de update fiind codificată prin caracterul $U$, iar o operaţie de tip query prin caracterul $Q$. În cazul în care este o operaţie de tip update, pe aceeaşi linie urmează încă două numere intregi $nr$ şi $id$, separate printr-un spaţiu, unde $nr$ reprezintă numărul de cetăţeni care apar/dispar în nodul $id$. În cazul în care este o operaţie de tip query, pe aceeaşi linie urmează un număr natural $id$, care reprezintă nodul care va deveni capitală şi pentru care vi se cere să aflaţi răspunsul.

Date de ieșire

Fişierul de ieşire rafaela.out va conţine pe fiecare linie câte un număr întreg, reprezentând răspunsurile (în ordine) pentru fiecare operaţie de tip query din fişierul de intrare.

Restricții și precizări

• $1 ≤ N ≤ 200 \ 000$
• $1 ≤ Q ≤ 200 \ 000$
• Se garantează că numărul total de cetăţeni, după fiecare operaţie update, se încadrează pe $32$ de biţi cu semn.
• Se garantează că numărul de cetăţeni dintr-un nod, după fiecare operaţie de update este un număr pozitiv (mai mare sau egal cu $0$).

Exemplu

rafaela.in

5 5
1 2
2 3
2 4
4 5
1 2 3 2 3
Q 2
U 10 3
Q 2
U -5 3
Q 1

rafaela.out

5 
13
15

Explicație

Pentru primul query răspunsul este $5$, muchia cea mai intens utilizată fiind cea dintre nodurile $2$ şi $4$ (se deplasează către capitala $2$ toţi cetăţenii din nodurile $4$ si $5$).

Pentru al doilea query, răspunsul este $13$, muchia cea mai utilizată fiind cea care uneşte nodul $2$ de nodul $3$ (nodul $3$ conţine $13$ cetăţeni, în urma operaţiei update).

Pentru al treilea query, răspunsul este $15$, muchia cea mai folosită fiind cea dintre nodul $1$ şi nodul $2$.