Adă caii

CJ și-a lăsat herghelia de cai liberă pe pajiștea de la Șumuștău și acum îl strigă pe JS să aducă caii înapoi. Pajiștea de la Șumuștău poate fi reprezentată sub forma unui arbore cu $N$ noduri indexate de la $1$ la $N$. Se știe că în nodul $i$ se află $C_i$ cai. Pe parcursul a $Q$ evenimente de timp, CJ și JS se plimbă pe pajiște ca să adune caii. Un eveniment poate fi unul din cele două tipuri de mai jos:

• CJ x: CJ vine în nodul $x$. Prin urmare, toți caii se mută, din nodul în care se află în nodul vecin cel mai apropiat de x. (Caii din nodul $x$ stau pe loc.)
• JS x y: JS spune că în nodul $x$ sunt $y$ cai și voi trebuie să stabiliți dacă minte sau nu.

Cerință

Se dau $N$, $Q$, numărul inițial de cai din fiecare nod, muchiile arborelui și cele $Q$ evenimente și se cere să se stabilească dacă JS spune adevărul pentru fiecare eveniment de tip JS ținând cont de modificările făcute de evenimentele CJ până în acel moment.

Date de intrare

Pe prima linie a intrării se află două numere naturale $N$ și $Q$ separate printr-un spațiu. Pe a doua linie se află $N$ numere naturale separate prin spații, cel de al $i$-lea număr reprezentând numărul inițial de cai din nodul $i$.

Pe următoarele $N-1$ linii se află câte două numere naturale $a$ și $b$ cu semnificația că există muchie de la nodul $a$ la nodul $b$.

Pe fiecare dintre următoarele $Q$ linii se va afla câte un eveniment din un din cele două tipuri

• Pentru evenimente de primul tip se dă un șir de forma CJ și separat printr-un spațiu un număr natural $x$ reprezentând nodul în care se duce CJ.
• Pentru evenimente de al doilea tip se dă un șir de forma JS și separate prin spații două numere naturale $x$ și $y$ reprezentând nodul în care vrem să numărăm câți cai există respectiv câți cai susține JS că sunt acolo.

Date de ieșire

Ieșirea trebuie să conțină un număr de rânduri egal cu numărul de evenimente de tip JS din intrare. Pe fiecare rând se va afișa $1$ dacă se stabilește că JS spune adevărul sau $0$ dacă se stabilește că JS minte.

Restricții și precizări

• $1 \leq N, Q \leq 100 \ 000$
• $0 \leq C_i \leq 1 \ 000 \ 000 \ 000$
• $1 \leq \sum_{i=1}^N C_i \leq 1 \ 000 \ 000 \ 000$
• $0 \leq y \leq 1 \ 000 \ 000 \ 000$ pentru toate evenimentele de tip JS
• $1 \leq x \leq N$ pentru toate evenimentele

Exemple

stdin

6 4
1 1 1 2 2 2
1 2
2 3
2 4
4 5
3 6
CJ 6
CJ 6
JS 6 4
JS 6 3

stdout

1
0

Explicații:
După primul eveniment caii ajung să se mute astfel:
0 3 1 2 0 3
După al doilea eveniment caii ajung să se mute astfel:
0 2 3 0 0 4
La al treilea eveniment până în acest moment în nodul 6 regăsim 4 cai deci JS a spus adevărul.
La al patrulea eveniment până în acest moment în nodul 6 regăsim 4 cai deci JS minte că ar fi 3.