Problem Description
One day, a couple of friends J and F were playing the game called “RiskCraft”. But J was so confused by what F told him that F almost wanted to bully him. At that time, the occurrence of cheat had exactly prevented J from being mistreated any longer.
Now it's the time for F to make the strategy. There are several forts on the map, and each of the two forts has only one route to connect them. What's more, F had been doing something quiet beyond the expectation. He just got each of the forts armed with a large amount of soldiers. But it seemed apparently that F knew J was cheating. So, F determined to alter the proportion of the army. J was definitely getting really misleading By F's distorted strategies. So, he was really anxious of seeking the help of you.
Please number the forts from 1 to n. For instance, the fort ith number of solider is w(i) ( ps. w(i) may be a negative number as F likes. How rediculous!!), there are several tips of instructions that J hope s could help you work out this dilemma problem.
1. CHANGE u t: this means that F has the intention that he really want to change present group of the soldiers in fort u to t.
2. QMAX u v : this actually indicates that J is curious about what is the max number of the soldiers of a certain forts on the way from u to v.
3. QSUM u v : this absolutely expressed that J furiously have the temptation to know the whole number of the army from fort u to fort v.
Input
There are several test cases.
In each test case, the first line is a positive integer n (1 <=n<=30000) means the number of fort.
The next n-1 lines include two numbers a, b (1<=a, b<=n) indicating there is a path between fort a and fort b.
The next line has n numbers, the i th number w(i) (-30000<=w(i)<=30000) means the amount of the army in fort i.
The following lines has a unique number q (0<=q<=200000), means the total operations in this test case.
Above all, q lines will be definitely displayed on screen, each line offers a string like 'CHANGE u t', 'QMAX u v' or 'QSUM u v'.
Output
For each string 'QMAX' or 'QSUM', give a number express the result of this request.
Sample Input
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
Sample Output
4
1
2
2
10
6
5
6
5
16
