Problem description

Niedługo mija 40 lat od powstania Liceum nr 14 w Bajtocławiu. Z tej okazji prezydent miasta postanowił wprowadzić system, którzy pozwoli mu określić, który nauczyciel pracuje najciężej i przyznać mu bardzo prestiżową nagrodę.

Niektórzy nauczyciele mają swoich podwładnych. Relacja podwładności jest przechodnia: jeśli A ma podwładnego B, który ma podwładnego C to C jest też podwładnym A. Nauczyciele są numerowani kolejnymi liczbami naturalnymi od 1 do N.

Dyrektor, który jest niczyim podwładnym, utożsamia się z numerem 1. Zapewnione jest, że wszyscy nauczyciele są podwładymi dyrektora. Relacje są acykliczne.

Prezydent chciałby już w trakcie roku szkolnego kontrolować postępy nauczycieli, dlatego poprosił Cię o pomoc. Twoim zadaniem jest wykonywanie tych operacji:

• Add(x, v) – zwiększ współczynnik pracy nauczyciela x o v (początkowo wszystkie są równe 0).
• Count(x) – policz sumę współczynników pracy grupy nauczycieli - podwładnych x’a oraz jego samego.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oddzielone pojedynczym odstępem i określające kolejno liczbę nauczycieli oraz liczbę operacji.

W kolejnych N − 1 wierszach znajduje się opis relacji. Opis każdej składa się z liczb u_i i v_i, określających, że v_i jest podwładnym u_i lub u_i jest podwładnym v_i.

W kolejnych Q wierszach znajdują się zapytania. Opis każdego zapytania zaczyna się od słowa Count, pojedynczego odstępu, a następnie liczby naturalnej x – co oznacza zapytanie o Count(x) albo od słowa Add, pojedynczego odstępu, a następnie liczb x i v oddzielonych pojedynczym odstępem – co oznacza Add(x,v).

Wyjście

Dla każdego zapytania zaczynającego się od słowa Count należy wypisać jedną liczbę całkowitą, określającą Count(x).

Ograniczenia

1 ≤ N ≤ 250 000, 1 ≤ Q ≤ 300 000, 1 ≤ v_x ≤ 1 000 000.

Przykład

7 9
1 5
2 1
2 3
4 2
4 6
7 6
Add 7 5
Count 7
Add 7 8
Add 1 10
Add 2 7
Add 5 7
Count 7
Count 6
Count 3

5
13
13
0