Description

一棵树有$n$ 个节点，编号为$1～n$ ，每个节点都有一个权值$w$ 。

完成以下操作：

①$CHANGE$ $u$ $t$ ，把节点$u$ 的权值修改为$t$ ；

②$QMAX$ $u$ $v$ ，询问从节点$u$ 到节点$v$ 路径上节点的最大权值；

③$QSUM$ $u$ $v$ ，询问从节点$u$ 到节点$v$ 路径上节点的权值和（注意：从节点$u$ 到节点$v$ 路径上的节点包括$u$ 和$v$ 自身）。

Format

Input

第$1$行包含一个整数$n$ ，表示节点的个数。

接下来的$n -1$行，每行都包含两个整数$a$ 和$b$ ，表示在节点$a$和节点$b$ 之间有一条边相连。

接下来的$n$行，第$i$行的整数$w_i$ 表示节点$i$ 的权值。

接下来的一行包含一个整数$q$ ，表示操作的总数。

最后有$q$ 行，每行都表示一种操作，操作形式如上所述。

其中，$1≤n ≤30000$，$0≤q ≤200000$，保证操作中每个节点的权值$w$ 都为$-30000～30000$。

Output

对每个$QMAX$或者$QSUM$的操作，都单行输出一个整数表示要求的结果。

Samples

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

来源

HYSBZ1036