Description

Original source: ZJOI 2008

There is a tree with $n$ nodes, numbered from $1$ to $n$. Each node has a weight $w$. You are required to perform the following operations on the tree:

1. CHANGE u t: Change the weight of node $u$ to $t$;
2. QMAX u v: Query the maximum weight of nodes on the path from node $u$ to node $v$;
3. QSUM u v: Query the sum of weights of nodes on the path from node $u$ to node $v$.

Note: The nodes on the path from node $u$ to node $v$ include both $u$ and $v$ themselves.

Input Format

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

Next, $n-1$ lines follow, each containing two integers $a$ and $b$, indicating an edge between node $a$ and node $b$;

The following line contains $n$ integers, where the $i$-th integer $w_i$ represents the weight of node $i$;

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

Subsequent $q$ lines each describe an operation in the form of CHANGE u t, QMAX u v, or QSUM u v.

Output Format

For each QMAX or QSUM operation, output an integer representing the result.

Sample 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

4
1
2
2
10
6
5
6
5
16

Constraints & Hints

For $100\%$ of the data, $1\le n \le 3\times 10^4$, $0 \le q \le 2\times 10^5$. It is guaranteed that during the operations, each node's weight $w$ is between $-30000$ and $30000$.