Problem Description

Xiao L and Xiao K are having a heated discussion.

(You do not need to know who said which line...)

“Do you know non-empty subsets?”

“Of course! For example, for the set $\{1,2,3\}$, all of its non-empty subsets are $\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}$.”

“Then do you know the XOR sum of the numbers in each non-empty subset?”

“I do! It is just $1,2,3,1⊕2=3,2⊕3=1,1⊕3=2,1⊕2⊕3=0$.”

“Then do you know what their total sum is? We call it the subset XOR sum.”

“Subset XOR sum... what a strange name, but I know it is $1+2+3+3+1+2+0=12$.”

“Then let me ask you, what is the subset XOR sum of $\{a_1,a_2,...,a_n\}$?”

“Just brute force it slowly!”

“What if $n\le 200000$?”

“...”

“What if we put the problem on a tree?”

“... Can you solve it then?”

“Of course... I cannot...”

Now only you can help Xiao L and Xiao K. Please solve this problem.

To express the statement more clearly, we explain it again.

There is a tree with $n$ nodes, and there are $m$ operations in total. These operations are given in order. Each operation is either a query or a modification.

Each query operation gives two node indices $a,b$. As is well known, there is a unique path between $a$ and $b$ on the tree. Let the multiset of node weights of all nodes on this path be $S$. You need to output the subset XOR sum of $S$. The answer is taken $mod\space(10^9+7)$.

Each modification operation gives two node indices $a,b$ and an integer value $c$. You need to XOR the weight of every node on the unique path from node $a$ to node $b$ by $c$.

Here, “set” means multiset.

Input Format

The first line contains three positive integers $n,m$.

The next $n-1$ lines each contain two positive integers $a,b$, meaning there is an edge between node $a$ and node $b$. There will be no multiple edges or self-loops.

The next line contains $n$ non-negative integers. The $i$-th non-negative integer is the initial weight of node $i$.

The next $m$ lines each contain several integers describing an operation. The first integer of each line is either $1$ or $2$. If it is $1$, then this operation is a query, and the next two numbers are $a,b$; if it is $2$, then this operation is a modification, and the next three numbers are $a,b,c$.

Output Format

For each query, output one line containing the answer.

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

Hint

Sample explanation:

For the first query, the path from $1$ to $1$ passes through node $1$, the multiset of node weights is $\{1\}$, and the subset XOR sum is $1$.

After two modifications, the weight of node $1$ is $0$, and the weight of node $3$ is $1$.

For the second query, the multiset of node weights on the path from $1$ to $3$ is $\{0,1\}$, and the subset XOR sum is $0+1+1=2$.

This problem has $10$ test points. Each test point is worth $10$ points, for a total of $100$ points.

Constraints:

For $100\%$ of the data, all input numbers are non-negative integers not greater than $10^9+7$, and $1\le a,b\le n$.

Translated by ChatGPT 5