洛谷树

题目背景

萌哒的 Created_equal 小仓鼠种了一棵洛谷树! (题目背景是辣鸡小仓鼠乱写的QAQ)。

题目描述

树是一个无环、联通的无向图,由 $n$ 个点和 $n-1$ 条边构成。树上两个点之间的路径被定义为他们之间的唯一一条简单路径——显然这是一条最短路径。 现在引入一个概念——子路径。假设树上两个点 $p_1$ 和 $p_n$ 之间的路径是$P = \langle p_1,p_2,p_3…p_n \rangle $,那么它的子路径被定义为某一条路径 $P'$,满足 $P'= \langle p_i,p_{i+1},p_{i+2}…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$ 操作,输出答案。

输入输出样例

输入样例 #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

输出样例 #1

14
26

说明

\_\_本题时限1s,内存限制128M,因新评测机速度较为接近NOIP评测机速度,请注意常数问题带来的影响。\_\_ 【数据范围】 ```cpp No n= q= 备注 1 100 5 无 2 100 20 无 3 100 100 无 4 5000 1000 无 5 5000 2000 无 6 5000 3000 无 7 10000 10000 第i条边连接第i个点和第i+1个点,且没有2操作 8 10000 20000 第i条边连接第i个点和第i+1个点,且没有2操作 9 10000 10000 第i条边连接第i个点和第i+1个点 10 10000 20000 第i条边连接第i个点和第i+1个点 11 10000 10000 没有2操作 12 10000 20000 没有2操作 13 20000 20000 没有2操作 14 30000 30000 没有2操作 15 30000 10000 无 16 20000 20000 无 17 20000 20000 无 18 30000 20000 无 19 20000 30000 无 20 30000 30000 无 ``` 对于 $100\%$ 的数据,所有边权小于等于 $1023$。