Problem Description
Miceren finds a huge country named HY. HY has N cities numbered from 1 to N connected by N − 1 bidirectional roads. There exists a path between any two cities.
It can be imagined as a tree with n vertices rooted at vertex 1.
Miceren wants to occupy some cities here. Each city has a value vi. (Notice that the value of a city may be negative. Nevertheless, Miceren wants to occupied this city.)
As some usual stories, someone named Cloud wants to "steal" some cities from Miceren.
At the beginning, Miceren and Cloud don't occupy any city.
In the following Q days, one of three events may happen
Miceren will walk from the a-th city to the b-th city and all cities visited in this trip will belong to Miceren. (1 ≤ a,b ≤ N)
Cloud will steal the x-th city. If Miceren occupied the x-th city before, Miceren will lost the control of this city. (1 ≤ x ≤ N)
Miceren will occupy the subtree rooted at x.(1 ≤ x ≤ N)
As Miceren's friend, you must tell Miceren the total value of all cities which belong to Miceren after each day.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begin with one integer N, indicating the number of cities in HY.
The next line contains N integer Vi, indicating the value of each city.
The next N − 1 lines contain the details of the roads. Each line contains two integers u, v meaning that there is a road between cities u and v.
The next line contains one integer Q.
The next Q lines contain the details of event. If the format is "1 a b", it means the first event happened where Miceren walks from a-th city to b-th city. If the format is “2 x”, it means the second event happened where Cloud "steal"s the x-th city. Otherwise the format is “3 x” and the third event happened where Micron occupied the subtree rooted at x.
T is about 100.
1 ≤ N,Q ≤ 100000.
−1000 ≤ Vi ≤ 1000.
The ratio of test cases with N > 100 is less than 5%.
Output
For each test queries, print the answer.
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
1 2
1 3
2 4
2 5
5 9
5 10
3 6
3 7
3 8
6
1 10 4
1 9 7
2 5
3 4
2 4
1 6 10
Sample Output
21
41
36
36
32
43
