Квіти

Обмеження: 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