There is a tree with $n$ nodes, numbered from $1$ to $n$. Each node has a weight $w$.

We will ask you to perform the following operations on this tree:

I. CHANGE u t: Change the weight of node $u$ to $t$. II. QMAX u v: Query the maximum weight among the nodes on the path between node $u$ and node $v$. III. QSUM u v: Query the sum of the weights of the nodes on the path between node $u$ and node $v$.

Note: The path between node $u$ and node $v$ includes $u$ and $v$ themselves.

Input

The first line of the input contains an integer $n$, representing the number of nodes.

The next $n-1$ lines each contain two integers $a$ and $b$, representing an edge between node $a$ and node $b$.

The next $n$ lines each contain an integer, where the integer on the $i$-th line represents the weight $w_i$ of node $i$.

The next line contains an integer $q$, representing the total number of operations.

The next $q$ lines each contain an operation in the form of CHANGE u t, QMAX u v, or QSUM u v.

For $100\%$ of the data, $1 \le n \le 30000$ and $0 \le q \le 200000$. During the operations, the weight $w$ of each node is guaranteed to be between $-30000$ and $30000$.

Output

For each QMAX or QSUM operation, output the result on a new line.

Examples

Input 1

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Output 1

4
1
2
2
10
6
5
6
5
16