Description

A tree is an undirected, connected graph without cycles, consisting of $n$ vertices and $n-1$ edges. The path between two vertices in a tree is defined as the unique simple path between them; this is obviously a shortest path.

Now we introduce the concept of a subpath. Suppose the path between two vertices $p_1$ and $p_n$ on the tree is $P = \langle p_1,p_2,p_3, \ldots, p_n \rangle$. A subpath is any path $P'$ such that $P'= \langle p_i,p_{i+1},p_{i+2},\ldots,p_j \rangle$, where $1\le i \le j \le n$. Clearly, the original path itself is a subpath, and any single vertex can also be considered a subpath.

We assign a weight to every edge. The adorable Sugar asks the little hamster: for any two vertices $u$ and $v$, can you quickly find the sum of the $\text{xor}$ values of edge weights over all subpaths along the path from $u$ to $v$. Specifically, take all subpaths on the path from $u$ to $v$, for each subpath compute the $\text{xor}$ of the edge weights it traverses, and finally sum up all these $\text{xor}$ values.

What? You do not know $\text{xor}$? Go Baidu it.

At this point, fjzzq2002 showed up: I also want you to support an operation that modifies the weight of an edge.

The little hamster is so "laji" that he certainly cannot solve this problem, so he turns to you for help.

Input Format

The first line contains two positive integers $n$ and $q$, denoting the number of vertices and the total number of operations.

Each of the next $n-1$ lines contains two positive integers $u,v$ and a non-negative integer $w$, indicating there is an edge of weight $w$ between vertices $u$ and $v$.

Each of the next $q$ lines is in the format 1 u v or 2 u v w.
If it is operation 1 u v, you need to output the sum of the $\text{xor}$ values of edge weights over all subpaths on the path from $u$ to $v$.
If it is operation 2 u v w, you need to change the weight of the edge between $u$ and $v$ to $w$, and it is guaranteed that this edge exists.

Output Format

For each operation of type 1, output the answer.

5 3
1 2 3
2 3 3
2 4 6
4 5 1
1 3 4
2 2 4 7
1 3 5

14
26

Hint

For $100\%$ of the testdata, all edge weights are at most $1023$.

Translated by ChatGPT 5