Given a tree with \(N\) nodes, rooted at node \(1\). Every node of tree has a value associated with it denoted by an array \(A\).

We perform \(Q\) queries of following \(2\) types on tree:

• \(1 \ u\) : Output the sum of values of all the nodes in subtree of \(u\) including \(u\).
• \(2 \ u \ p\) : For all the nodes in subtree of \(u\) including \(u\), perform Bitwise XOR operation of their value with \(p\). That mean \(A_i = A_i \newcommand*\xor{\oplus} p\) where \(i\) will be the node in subtree of \(u\) including \(u\) (where \(\newcommand*\xor{\oplus}\) denotes the Bitwise XOR operator).

Find the output for all the queries of type \(1\).

Input format

• First line contains \(N\) denoting the number of nodes in the tree.
• Next \(N-1\) lines contain two space-separated integers \(u\), \(v\) denoting an edge between node \(u \) and \(v\).
• Next line has \(N\) space separated integers denoting the array \(A\)
• Next line contains \(Q\) denoting the number of queries.
• Next \(Q\) lines contain description of queries.

It is guaranteed that there will be at least one query of type \(1\).

Output format

For each query of type \(1\) print a single integer denoting the answer to that query in a separate line.

Constraints

\(1 \le N, Q \le 10^5 \\ 1 \le A[i], p \le 10^5\)