题目描述

小 Q 是一个热爱学习的人，他经常去维基百科学习计算机科学。

就在刚才，小 Q 认真地学习了一系列位运算符，其中按位异或的运算符 $\oplus$ 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律，即 $i \oplus j = j \oplus i$。

他发现，按位异或可以理解成被运算的数字的二进制位对应位如果相同，则结果的该位置为 $0$，否则为 $1$，例如：$1(01) \oplus 2(10) = 3(11)$。

他还发现，按位异或可以理解成参与运算的数字的每个二进制位都进行了不进位的加法，例如：$3(11) \oplus 3(11) = 0(00)$。

现在小 Q 有一棵 $n$ 个结点的无根树 $T$，结点依次编号为 $1$ 到 $n$，其中结点 $i$ 的权值为 $v_i$。 定义一棵树的价值为它所有点的权值的异或和，一棵树 $ T $ 的连通子树就是它的一个连通子图，并且这个图也是一棵树。 小 Q 想要在这棵树上玩切树游戏，他会不断做以下两种操作：

• Change x y，将编号为 $x$ 的结点的权值修改为 $y$。
• Query k，询问有多少棵 $T$ 的非空连通子树，满足其价值恰好为 $k$。

小 Q 非常喜（bu）欢（hui）数学，他希望你能快速回答他的问题，你能写个程序帮帮他吗？

输入格式

第一行包含两个正整数 $n$，$m$，分别表示结点的个数以及权值的上限。
第二行包含 $n$ 个非负整数 $v_1, v_2, \dots, v_n$，分别表示每个结点一开始的权值。
接下来 $n − 1$ 行，每行包含两个正整数 $a_i$，$b_i$，表示有一条连接 $a_i$ 和 $b_i$ 的无向树边。
接下来一行包含一个正整数 $q$，表示小 Q 操作的次数。
接下来 $q$ 行每行依次表示每个操作。

输出格式

输出若干行，每行一个整数，依次回答每个询问。因为答案可能很大，所以请对 $10007$ 取模输出。

样例

input

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

3
3
2
3
2
4
2
3

数据范围与提示

对于 $100\%$ 的数据，$1 \leq a_i, b_i, x \leq n$，$0 \leq v_i, y, k < m$，修改操作不超过 $10000$ 个。