You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

萌哒的 Created_equal 小仓鼠种了一棵洛谷树！

（题目背景是辣鸡小仓鼠乱写的 QAQ）。

题目描述

树是一个无环、连通的无向图，由 $n$ 个点和 $n-1$ 条边构成。树上两个点之间的路径被定义为他们之间的唯一一条简单路径——显然这是一条最短路径。

现在引入一个概念——子路径。假设树上两个点 $p_1$ 和 $p_n$ 之间的路径是 $P = \langle p_1,p_2,p_3, \ldots, p_n \rangle$，那么它的子路径被定义为某一条路径 $P'$，满足 $P'= \langle p_i,p_{i+1},p_{i+2},\ldots,p_j \rangle$，其中 $1\le i \le j \le n$。显然，原路径是一条子路径，任意一个点也可以作为子路径。

我们给每条边赋予一个边权。萌萌哒的 Sugar 问小仓鼠：对于任意两个点 $u$ 和 $v$，你能快速求出，$u$ 到 $v$ 的路径上所有子路径经过的边的边权的 $\text{xor}$ 值的和是多少。具体地说就是，你把 $u$ 到 $v$ 的路径上所有子路径全部提出来，然后分别把每个子路径上经过的边的边权 $\text{xor}$ 在一起，最后求出得到的所有 $\text{xor}$ 值的和。

什么？你不知道 $\text{xor}$？那就去百度啊！

这时候，fjzzq2002 大爷冒了粗来：窝还要你滋磁修改某条边边权的操作！

小仓鼠那么辣鸡，当然不会做这道题啦。于是他就来向你求救！

输入格式

第一行两个正整数 $n$ 和 $q$，表示点的个数，查询和询问的总次数。

接下来 $n-1$ 行，每行两个正整数 $u,v$ 和一个非负整数 $w$，表示 $u$ 和 $v$ 两个点之间有一条边权为 $w$ 的边。

接下来 $q$ 行，格式为 1 u v 或 2 u v w。
如果为 1 u v 操作，你需要输出 $u$ 到 $v$ 的路径上所有子路径经过的边的边权的 $\text{xor}$ 值的和是多少。
如果为 2 u v w 操作，你需要把 $u$ 到 $v$ 这条边的边权改为 $w$，保证这条边存在。

输出格式

对于每个 $1$ 操作，输出答案。

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

提示

测试点编号	$n=$	$q=$	备注
$1$	$100$	$5$	无
$2$		$20$
$3$		$100$
$4$	$5\times 10^3$	$10^3$
$5$		$2\times 10^3$
$6$		$3\times 10^3$
$7$	$10^4$	$10^4$	第 $i$ 条边连接第 $i$ 个点和第 $i+1$ 个点，且没有 $2$ 操作
$8$		$2\times 10^4$
$9$		$10^4$	第 $i$ 条边连接第 $i$ 个点和第 $i+1$ 个点
$10$		$2\times 10^4$
$11$		$10^4$	没有 $2$ 操作
$12$		$2\times 10^4$
$13$	$2\times 10^4$
$14$	$3\times 10^4$	$3\times 10^4$
$15$		$10^4$	无
$16$	$2\times 10^4$	$2\times 10^4$
$17$
$18$	$3\times 10^4$
$19$	$2\times 10^4$	$3\times 10^4$
$20$	$3\times 10^4$

对于 $100\%$ 的数据，所有边权小于等于 $1023$。