supertree

Se da un arbore cu N noduri numerotate de la 1 la N, fiecare nod avand asociat cate o valoare. Asupra arborelui se efectueaza M operatii. Fiecare operatie este de tip Q - query sau U - update. Fiecare operatie de ambele tipuri este la randuri ei de mai multe tipuri:

• 1 x Operatia se executa asupra nodului x
• 2 x Operatia se executa asupra tuturor nodurilor din subarborele lui x (radacina arborelui este 1)
• 3 x y Operatia se executa asupra tuturor nodurilor din lantul ce uneste nodurile x si y

Daca operatia este de tip Q se va afisa pe cate o linie suma nodurilor asupra careia este efectuata operatia. Daca operatia este de tip U se va citi si un numar z la final, cu semnificatia ca fiecare nod asupra caruia se efectueaza operatia devine egal cu z.

Date de intrare

Pe prima linie se citesc numarele N si M. Pe urmatoarea linie se citesc valorile nodurilor de la 1 la N. Pe urmatoarele N - 1 se citesc muchiile arborelui. Pe urmatoarele M linii se citesc operatiile dupa formatul de mai sus.

Date de iesire

Se va afisa rezultatul operatiilor de tip Q.

Restrictii si precizari

• 1 ≤ N, Q ≤ 200 000
• Valorile nodurilor vor fi mereu numere pozitive ≤ 1 000 000 000

Exemplu

stdin

11 8
1 2 1 3 1 1 2 1 1 3 1
1 2
1 3
2 4
2 5
4 6
4 9
4 8
3 7
7 10
7 11
Q 2 2
U 3 6 7 4
Q 1 8
Q 1 4
U 1 1 5
Q 3 5 10
U 2 7 2
Q 2 1

stdout

9
1
4
21
30

Explicatii

Spre exemplu, operatia U 3 6 7 4 este o operatie update de tip 3, adica nodurile de pe lantul 6 - 7 devine toate egale cu 4. Operatia Q 2 1 este o operatie de tip query in care ni se cere sa afisam suma tuturor nodurilor din subarborele nodului 1