Little Q is a person who loves to learn, and he often visits Wikipedia to study computer science.

Just now, Little Q has been diligently studying a series of bitwise operators, among which the bitwise XOR operator $\oplus$ has made a great impression on him. The bitwise XOR operator is a binary operator. Bitwise XOR is commutative, i.e., $i \oplus j = j \oplus i$.

He discovered that bitwise XOR can be understood as follows: for the binary representations of the numbers being operated on, if the bits at the corresponding positions are the same, the result at that position is 0; otherwise, it is 1. For example: $1(01) \oplus 2(10) = 3(11)$.

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

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

The value of a tree is defined as the XOR sum 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.

Little Q wants to play a tree-cutting game on this tree, and he will continuously perform the following two types of operations:

• Change x y: Change the weight of node $x$ to $y$.
• Query k: Query how many non-empty connected subtrees of $T$ have a value exactly equal to $k$.

Little Q likes (or rather, dislikes) mathematics, and he hopes you can answer his questions quickly. Can you write a program to help him?

Input

The first line contains two positive integers $n, m$, representing the number of nodes and the upper bound of the weights, respectively.

The second line contains $n$ non-negative 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$, representing an undirected edge connecting $a_i$ and $b_i$.

The next line contains a positive integer $q$, representing the number of operations Little Q performs.

The next $q$ lines each describe an operation.

Output

Output several lines, each containing an integer, answering each query in order. Since the answer can be very large, please output the result modulo $10007$.

Examples

Input 1

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

Output 1

3
3
2
3
2
4
2
3

Note

For 100% of the data, $1 \le a_i, b_i, x \le n$, $0 \le v_i, y, k < m$, and there are no more than $10000$ modification operations.