背景

刚才，Doctor Who在餐厅里招待了Clara。

描述

TARDIS上有\( n\)个房间，编号分别为\(1\)到\(n\)，每个房间都有一个门牌号\(w\)。

Doctor Who兴致勃勃地希望Clara完成以下操作：

I.CHANGE u t: 把房间\(u\)的门牌号改为\(t\)。

II.QMAX u v: 询问从房间\( u\)到房间\(v \)的路径上的房间的最大门牌号。

III.QSUM u v问从房间\( u\)到房间\( v\)的路径上的房间的门牌号和。

注意：从点\(u \)到点\(v \)的路径上的房间包括\( u\)和\( v\)本身。

格式

输入格式

输入文件的第一行为一个整数\(n\)，表示房间的个数。

接下来\( n-1\)行，每行\( 2\)个整数\(a \)和\(b\)，表示房间\(a \)和房间\(b \)之间有一条走廊相连。

接下来一行\(n\)个整数，第\( i\)个整数\( w_i\)表示节点房间\(i \)的门牌号。

接下来\( 1\)行，为一个整数\( q\)，表示操作的总数。

接下来\(q \)行，每行一个操作，以CHANGE u t或者QMAX u v或者QSUM u v的形式给出。

输出格式

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

样例1

输入样例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

输出样例1

4
1
2
2
10
6
5
6
5
16

限制

对于\( 100 \%\)的数据，保证\( 1\le n \le 3\times 10^4，0\le q\le 2\times 10^5\)。

中途操作中保证每个房间的门牌号\(w \)在\( -3\times 10^4\)到\( 3\times 10^4\)之间。