XOR Subtree Queries

Little Q loves learning and has recently studied a series of bitwise operators on Wikipedia. Among these, the bitwise XOR operator \(\oplus\) had a significant impact on him. Recall that for two numbers, the bitwise XOR \(i \oplus j\) produces a binary digit of 0 if the corresponding bits of \(i\) and \(j\) are the same, and 1 otherwise. For example, \(1(01) \oplus 2(10) = 3(11)\) and \(3(11) \oplus 3(11) = 0(00)\>.

You are given an unrooted tree \(T\) with \(n\) nodes numbered from \(1\) to \(n\). The weight of node \(i\) is \(v_i\). The value of a tree is defined as the XOR (\(\oplus\)) of all its node weights. A connected subtree of \(T\) is any connected subgraph of \(T\) that is also a tree.

Little Q plays a game on this tree by performing the following operations repeatedly:

• Change x y: Change the weight of node \(x\) to \(y\).
• Query k: Count the number of non-empty connected subtrees of \(T\) whose value is exactly \(k\).

Your task is to process these operations. Note that \(\oplus\) is commutative, that is, \(i \oplus j = j \oplus i\). You can assume that \(n \leq 15\) so that even brute force enumeration of all \(2^n - 1\) non-empty subsets is feasible.

inputFormat

The input format is as follows:

1. A line containing an integer \(n\), the number of nodes in the tree (\(n \leq 15\)).
2. A line with \(n\) space-separated integers \(v_1, v_2, \ldots, v_n\) representing the initial weights of the nodes.
3. \(n-1\) lines each containing two space-separated integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\).
4. A line containing an integer \(m\), the number of operations.
5. \(m\) lines each describing an operation in one of the following formats:
   • Change x y: Update the weight of node \(x\) to \(y\).
   • Query k: Query the number of connected subtrees whose XOR value is \(k\).

outputFormat

For each Query operation, print a single integer on a new line representing the count of connected subtrees whose XOR sum equals the queried value \(k\).

sample

3
1 2 3
1 2
2 3
3
Query 0
Change 2 5
Query 1

1
1