Квіти

Обмеження: 2 сек., 256 МіБ

Джон і Брюс часто відвідують ліс неподалік свого будинку. У лісі є $n$ прекрасних полян і $n-1$ двостороння стежка. Кожна стежина з’єднує дві поляни. З кожної поляни стежками можна добратися до будь-якої іншої. Тому є рівно один простий шлях (тобто шлях, який складається з різних стежок) від однієї поляни до іншої.

Джон: Брюсе, ці квіти для тебе!

Брюс: Чудово, вони прекрасні! Але чому їх тільки чотири?

Хлопці відвідуватимуть ліс упродовж $m$ днів поспіль. Перед першим днем на $i$-й поляні росте $f_i$ дуже гарних квітів. На початку кожного дня на кожній поляні з’являтиметься по одній додатковій квітці.

Після цього Джон і Брюс або зірвуть усі квіти на поляні, або порахують кількість квіток на простому шляху між двома полянами включно.

Вхідні дані

У першому рядку задано два цілі числа $n$ і $m$.

Наступний рядок містить $n$ цілих чисел $f_i$.

Кожен із наступних $n-1$ рядків містить цілі числа $a_i$ та $b_i$ — поляни, з’єднані $i$-ою стежкою.

Кожен із наступних $m$ рядків починається з одного символа (P чи C). Якщо це P, то після нього слідує ціле число $g_i$ — це значить, що в $i$-ий день хлопці зірвуть усі квіти на поляні $g_i$. Інакше після символа C слідують два цілі числа $u_i$ та $v_i$. У цьому разі Джон і Брюс порахують кількість квітів на простому шляху між полянами $u_i$ та $v_i$ включно.

Вихідні дані

Для кожного підрахунку виведіть рядок, що містить обчислену кількість квітів.

Обмеження

$1 \le n, m \le 10^5$,

$0 \le f_i \le 10^9$,

$1 \le a_i, b_i, g_i, u_i, v_i \le n$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 3 4 7 1 2 C 1 2 P 2 C 1 2	13 8

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 1 100 C 1 1	101