Tokitsukaze and Colorful Tree

Problem Description

Tokitsukaze has a rooted tree with $n$ nodes, whose nodes are labeled from $1$ to $n$ and whose root is node $1$. Furthermore, each node $i$ has its own color $col_i$ and its own weight $val_i$, where the color is labeled as a number between $1$ and $n$, representing one of $n$ given colors. Here are two types of operation: ● $1$ $x$ $v$ -- set $val_x$ as $v$. ● $2$ $x$ $c$ -- set $col_x$ as $c$. Tokitsukaze wants to execute $q$ opeations and for $i = 1, 2, \ldots, q + 1$, after finishing the first $(i - 1)$ operations, she wants to know the value of $$\sum_{\substack{1 \leq u < v \leq n \ col_u = col_v \ \text{node }u\text{ is not an ancestor of node }v \ \text{node }v\text{ is not an ancestor of node }u}}{(val_u \oplus val_v)}$$ where $\oplus$ is the bitwise exclusive OR operation. If you are not familiar with the bitwise exclusive OR, you may refer to http://en.wikipedia.org/wiki/Bitwise_operation#XOR and http://baike.baidu.com/item/xor/64178 .

Input

There are several test cases. The first line contains an integer $T$ ($1 \leq T \leq 8$), denoting the number of test cases. Then follow all the test cases. For each test case, the first line contains an integer $n$ $(1 \leq n \leq 10^5)$, denoting the number of nodes. The second line contains $n$ integers, where the $i$-th intger is $col_i$ $(1 \leq col_i \leq n)$, denoting the color of node $i$ at the beginning. The third line contains $n$ integers, where the $i$-th intger is $val_i$ $(0 \leq val_i < 2^{20})$, denoting the weight of node $i$ at the beginning. The next $(n - 1)$ lines describe the tree, where each line contains two integers $u$ and $v$ $(1 \leq u, v \leq n)$, representing an edge connecting node $u$ and node $v$. The next line contains an integer $q$ $(0 \leq q \leq 10^5)$, denoting the number of operations. The next $q$ lines describe these operations in chronological order of occurrence, where each line contains three integers such that ● if the first integer is $1$, then the following two integers are $x$ and $v$ $(1 \leq x \leq n, 0 \leq v < 2^{20})$, representing an operation of the first type, or ● otherwise the first integer is $2$, and the following two integers are $x$ and $c$ $(1 \leq x, c \leq n)$, representing an operation of the second type. It is guaranteed that the size of the standard input file does not exceed $32$ MiB, so you may need to use a fast approach to read the input data.

Output

For each test case, output $(q + 1)$ lines, where the $i$-th line contains an integer, denoting the value Tokitsukaze wants to know after the first $(i - 1)$ operations.

Sample Input

1
5
1 1 1 1 1
1 2 4 8 16
1 2
3 1
2 4
2 5
2
1 3 32
2 3 2

Sample Output

62
146
24

Hint

For the only sample case: ● before the first operation, the value is (2 ⊕ 4) + (4 ⊕ 8) + (4 ⊕ 16) + (8 ⊕ 16) = 6 + 12 + 20 + 24 = 62; ● before the second operation, the value is (2 ⊕ 32) + (32 ⊕ 8) + (32 ⊕ 16) + (8 ⊕ 16) = 34 + 40 + 48 + 24 = 146; ● after all the operations, the value is 8 ⊕ 16 = 24.

Source

2020 Multi-University Training Contest 3