题目描述

小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$。