搬砖的JoneySun

Tags:

Description

JoneySun欧皇附体一发入魂，成功消灭了wifepie逃出了监狱。他回到了家中继续自己的搬砖生活。因为成功消灭了邪恶的wifepie，村长BambooCertain决定给他加个buff，每当JoneySun去到一个地点搬砖，BambooCertain就会通过一些手段给改变JoneySun搬的砖的数量，当然每个地点的砖的数量不一定是一样的，JoneySun每天搬砖的地点也是不一样的。

假设共有$n$个搬砖的地点，所有的搬砖地点由$n-1$条路相连，任意两个地点之间相互连通。每次JoneySun会选定一个地点$x$，并将其它地点的砖搬到$x$。每搬一个地点的砖JoneySun都必须把砖先搬回$x$再去搬下一个地点的砖，在JoneySun回到$x$之前BanbooCertain会给JoneySun加上一个buff，这个buff会使JoneySun手头的砖的数量改变，假如joney手上砖的数量是$y$，那么加上buff后砖的数量会变为$y\bigoplus w$,其中$w$是一个与搬砖地点有关的整数。同时地点$x$的砖的数量也可能在某天发生变化。

说人话就是，你将得到一颗树，树上共有$n$个点，每个点有点权，每条边有边权，对于这颗树你需要完成以下两个操作：

1. 修改点$x$的权值
2. 对于点$x$，查询除$x$外所有点的点权与$x$到该点路径上距离$x$点最近的边的边权的异或值之和

Input

第一行一个整数$n(1\le n \le 10^5)$表示树上点的数量

接下来$n-1$行每行$3$个整数$u,v,w,(1\le u ,v \le n,1\le w \lt 2^{20})$表示树上每条边及边权

每个结点的初始点权为$0$

接下来一行一个整数$m$表示$m$次操作

接下来$m$行每行第一个数字$opt$表示操作类型

• $opt=1$接下来两个整数$x,(1\le x \le n),y(1\le y \lt 2^{20})$表示将$x$点的权值修改为$y$
• $opt=2$接下来一个整数$x$，表示查询除$x$外所有点的点权与$x$到该点路径上距离$x$点最近的边的边权的异或值之和

Output

对于每个操作$2$，输出一个整数表示答案

Samples

Hint

Author