HZNUOJ

搬砖的JoneySun

Tags:
Time Limit:  2 s      Memory Limit:   256 MB
Submission:53     AC:21     Score:100.00

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$表示操作类型



Output

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

Samples

input
5 2 1 1 3 1 1 4 1 1 5 1 1 5 1 2 1 1 1 4 2 1 1 5 1 2 1
output
3 2

Hint

Author

BAO, Min