Root Changes

A tree (connected acyclic graph) with N vertices, numbered from 1 to N, where each vertex of the tree has a positive integer weight denoted by W~_i~ for vertex i is given. Initially, we consider the root of the tree to be vertex 1.

In such a tree, we can perform two types of operations:

• R r: Change the root of the tree so that the new root is vertex r.
• S u: Query - Find the sum of the weights of the vertices in the subtree rooted at vertex u.

Input:

The first line of input will contain two positive integers N and Q, the number of vertices in the tree and the number of operations to perform, respectively. The second line contains N positive integers, where the i-th integer represents the weight of vertex i, denoted by W~_i~, where 1 ~\le~ W~_i \le 10^6~. The next N-1 lines of input describe the tree, where each line contains two positive integers u and v, from 1 to N, indicating that vertices u and v are connected by an edge. Then, there are Q lines, each representing an operation, either of the form "R r" or "S u".

Note: In the case of an operation of the form 'R r', nothing needs to be printed; we simply execute the change of the tree's root.

Output:

For each query of the form "S u" read from the input, in order, print one line containing a positive integer: the sum of the weights of the vertices in the subtree rooted at vertex u with the current tree structure.

Note: All data is read from standard input and printed to standard output.

Constraints:

• For subtasks worth 20% of the total points, it will be:
  1 ~\le~ Ν ~\le~ 1000, 1 ~\le~ Q ~\le~ 1000
• For subtasks worth 50% of the total points, iit will be:
  1 ~\le~ Ν ~\le~ 2000, 1 ~\le~ Q ~\le~ 100000
• For the full score subtask, it will be:
  1 ~\le~ Ν ~\le~ 100000, 1 ~\le~ Q ~\le~ 100000

Example of Input - Output:

input

7 7
3 2 7 8 4 1 1
1 2
1 3
2 7
3 4
3 5
3 6
S 1
S 3
R 3
S 1
R 2
S 2
S 3

output

26
20
6
26
20

Explanation of the Example:

The vector of weights of the tree's vertices is as follows: W~_1~ = 3, W~_2~ = 2,W~_3~ = 7, W~_4~ = 8, W~_5~ = 4, W~_6~ = 1, W~_7~ = 1.

The tree goes through three phases: the initial phase where the root is vertex 1, a second phase where the root becomes vertex 3, and the final phase where the root becomes vertex 2. These three phases are illustrated below:

In the first operation (query S 1), we are in the first phase with the root being vertex 1, and the answer is equal to the sum of weights of all vertices: W~_1~+W~_2~+W~_3~+W~_4~+W~_5~+W~_6~+W~_7~ = 3+2+7+8+4+1+1 = 26.

• In the second operation (query S 3), we still have the root as vertex 1, so the answer is: W~_3~+W~_4~+W~_5~+W~_6~ = 7+8+4+1 = 20.
• In the third operation (change root R 3), we transition to the second phase with the root being vertex 3.
• In the fourth operation (query S 1), the answer is W~_1~+W~_2~+W~_7~ = 3+2+1 = 6.
• In the fifth operation (change root R 2), we transition to the third phase with the root being vertex 2.
• In the sixth operation (query S 2), the answer is W~_1~+W~_2~+W~_3~+W~_4~+W~_5~+W~_6~+W~_7~= 3+2+7+8+4+1+1 = 26.
• In the seventh and final operation (query S 3), the answer is W~_3~+W~_4~+W~_5~+W~_6~ = 7+8+4+1 = 20.