Description

Xiao Q is someone who loves to learn. He often goes to Wikipedia to study computer science.

Just now, Xiao Q carefully studied a series of bitwise operators, among which the bitwise XOR operator $\oplus$ impressed him a lot. The bitwise XOR operator is a binary operator. Bitwise XOR is commutative, i.e., $i \oplus j = j \oplus i$.

He found that bitwise XOR can be understood as: for the binary representations of the numbers being operated on, if the corresponding bits are the same, then the result’s bit is $0$, otherwise it is $1$, for example: $1(01) \oplus 2(10) = 3(11)$.

He also found that bitwise XOR can be understood as performing addition without carry on each binary bit of the numbers involved, for example: $3(11) \oplus 3(11) = 0(00)$.

Now Xiao Q has an unrooted tree $T$ with $n$ nodes, numbered from $1$ to $n$, where the weight of node $i$ is $v_i$.

Define the value of a tree as the XOR of the weights of all its nodes. A connected subtree of a tree $T$ is a connected subgraph of $T$ that is also a tree.

Xiao Q wants to play a cut-tree game on this tree. He will repeatedly perform the following two operations:

• Change x y: change the weight of node $x$ to $y$.
• Query k: ask how many nonempty connected subtrees of $T$ have value exactly $k$.

Xiao Q really likes (but is not good at) math, and he hopes you can answer his questions quickly. Can you write a program to help him?

Input Format

• The first line contains two positive integers $n$, $m$, representing the number of nodes and the upper bound of weights.
• The second line contains $n$ nonnegative integers $v_1, v_2, \dots, v_n$, representing the initial weight of each node.
• The next $n - 1$ lines each contain two positive integers $a_i$, $b_i$, indicating that there is an undirected tree edge connecting $a_i$ and $b_i$.
• The next line contains a positive integer $q$, representing the number of operations Xiao Q performs.
• The next $q$ lines each describe one operation in order.

Output Format

Output several lines, each containing one integer, answering each query in order. Since the answer may be large, output it modulo $10007$.

4 4
2 0 1 3
1 2
1 3
1 4
12
Query 0
Query 1
Query 2
Query 3
Change 1 0
Change 2 1
Change 3 3
Change 4 1
Query 0
Query 1
Query 2
Query 3

3
3
2
3
2
4
2
3

Hint

Constraints: For $100\%$ of the testdata, $1 \leq a_i, b_i, x \leq n$, $0 \leq v_i, y, k < m$, and the number of Change operations does not exceed $10000$.

Translated by ChatGPT 5