The Flowers

Limits: 2 sec., 256 MiB

John and Brus often visit a forest not far from their home. There are $N$ beautiful glades and $N-1$ two-way footpaths in the forest. Each footpath connects two glades. Also it’s possible to get from any glade to any other using footpaths. Thus there is exactly one simple path (i.e. path that consists of distinct glades) from one glade to another.

John: Brus, these flowers are for you!

Brus: Nice, they are beautiful! But why there are four of them?

Guys will visit the forest for $M$ successive days. Before the first day there are $F_i$ very beautiful flowers growing on $i$-th glade. At the beginning of each day one additional flower will appear on each glade. After that John and Brus will either pick all the flowers on a glade or calculate the number of flowers on the simple path between two glades inclusive.

Input

A test case starts with a line containing integers $N$ and $M$. The following line contains $N$ integers $F_i$. Each of next $N-1$ lines contains integers $A_i$ and $B_i$ — the glades connected by $i$-th footpath. Each of next $M$ lines starts with a single character (‘P’ or ‘C’). If it is ‘P’ then it will be followed by integer $G_i$ and it means that on $i$-th day guys will pick all the flowers on glade $G_i$. Otherwise ‘C’ character will be followed by integers $U_i$ and $V_i$. In this case John and Brus will calculate the numbers of flowers on a simple path between glades $U_i$ and $V_i$ inclusive. All the integers in a single line are separated by single spaces.

Output

For each calculation print a single line containing desired number of flowers.

Constraints

$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$.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 3 4 7 1 2 C 1 2 P 2 C 1 2	13 8

Input (stdin) сopy	Output (stdout) сopy
1 1 100 C 1 1	101