LL meets a difficult problem about tree recently. There is a tree, the root's label is 1.Each node has a positive weight. There are two operations on the tree:

C x vchange the weight of node x to v

Q xsum up all W_u*W_v(W_u represents the weight of node u, W_v represents the weight of node v), the node u must be in the subtree whose root is node x, and the weight of node u must be an odd number. the node v can’t be in the subtree whose root is node x, and the weight of node v must be an even number.

The first line contains a number T(0<T≤10),represents the number of test case.

For each case, the first line contains a integer number N(1≤N≤10^5),represents the node's number of tree.

Next one line contains N integer numbers a_i (1≤a_i≤10^4),represent each node's weight.

Next N-1 lines, each line contains two number u,v(1≤u,v≤N),represents there is a edge to connect u and v.You may assume that they must form a tree.

Next one line contains a number M(1≤M≤10^5),represents the number of operations.

Last M lines represent M time operations.

For each case, first output “Case #t:”,t starts form 1.

For each Q operation,output the result.

2

3

2 2 3

1 2

2 3

1

Q 2

5

2 5 4 7 8

1 2

1 5

2 3

2 4

4

Q 2

Q 1

C 2 6

Q 2

Case #1:
6
Case #2:
120
0
70