子异和

小L和小K正在激烈地讨论着。 （你不用知道谁说的哪句话……） “你知道非空子集吗？” “当然知道啊！比如说集合$\{1,2,3\}$，它的所有非空子集就是$\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}$。” “那你知道每个非空子集里的数的亦或和是多少吗？” “也知道啊，不就是$1,2,3,1⊕2=3,2⊕3=1,1⊕3=2,1⊕2⊕3=0$吗。” “那你知道它们的和是多少吗？我们把它叫做子异和。” “子异和……这个名字好奇怪啊，不过我知道，是$1+2+3+3+1+2+0=12$。” “那我问你，$\{a_1,a_2,...,a_n\}$的子异和是多少？” “慢慢暴力算呗！” “如果$n\le 200000$呢？” “……” “如果把问题放在一颗树上呢？” “……那你会不会做啊？” “当然……不会做……” 现在，只有你能帮助小L和小K了，请你帮忙解决这个问题。 **为了更清晰的表达题意，我们再做一次解释。** 有一个$n$个节点的树，总共有$m$次操作。这些操作按照操作顺序输入。每次操作可能是询问或修改。 每次询问操作会给出两个节点编号$a,b$。根据常识，$a,b$在树上有唯一路径。我们设这条路径经过的所有点的点权集合为$S$。你要输出$S$的子异和。答案$mod\space(10^9+7)$。 每次修改操作会给出两个节点编号$a,b$与一个整数值$c$。你要将节点$a$到节点$b$的唯一路径上的所有点的点权分别异或$c$。 **这里的集合指可重集合**

第一行三个正整数$n,m$。 接下来$n-1$行，每行两个正整数$a,b$，表示节点$a$和$b$之间有一条边。不会出现重边与自环。 接下来一行$n$个非负整数，第$i$个非负整数表示$i$节点的初始点权。 接下来$m$行，每行若干个整数，表示$m$个操作的信息。每行第一个整数只可能是$1$或$2$。如果是$1$，则此操作为询问，接下来两个数为$a,b$；如果是$2$，则此操作为修改，接下来三个数为$a,b,c$。

对于每一个询问，输出一行表示答案。

3 4
1 2
1 3
1 1 1
1 1 1
2 1 3 1
2 3 3 1
1 1 3

1
2

样例解释： 第一次询问，$1$到$1$的路径经过$1$号节点，点权组成的集合为$\{1\}$，子异和为$1$。 两次修改后，$1$号点点权为$0$，$3$号点点权为$1$。 第二次询问，$1$到$3$的路径经过的点权集合为$\{0,1\}$，子异和为$0+1+1=2$。 本题共有$10$个测试点，每个测试点$10$分，总分为$100$分。 | 测试点编号 | $n$的范围 | $m$的范围 |特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1-2$ | $1\le n\le 1000$ | $1\le m\le 1000$ | 无 | | $3-5$ | $1\le n\le 200000$ | $1\le m\le 200000$ | 每条边连接的两个节点编号均相邻 | | $6-10$ | $1\le n\le 200000$ | $1\le m\le 200000$ | 无 | 对于$100\%$的数据： 输入的数均为不大于$10^9+7$的非负整数，$1\le a,b\le n$。