题目描述

由乃正在做她的 OJ 。现在她在处理 OJ 上的用户排名问题。 OJ 上注册了 $n$ 个用户，编号为 $1-n$，一开始他们按照编号排名。由乃会按照心情对这些用户做以下四种操作，修改用户的排名和编号：然而由乃心情非常不好，因为 Deus 天天问她题。。。因为 Deus 天天问由乃 OI 题，所以由乃去学习了一下 OI，由于由乃智商挺高，所以 OI 学的特别熟练她在 RBOI2016 中以第一名的成绩进入省队，参加了 NOI2016 获得了金牌保送。

Deus：这个题怎么做呀？

yuno：这个不是 NOI2014 的水题吗。。。

Deus：那如果出到树上，多组链询问，带修改呢？

yuno：诶。。。？？？

Deus：这题叫做睡觉困难综合征哟~

虽然由乃 OI 很好，但是她基本上不会 DS，线段树都只会口胡，比如她 NOI2016 的分数就是 $100+100+100+0+100+100$。。。NOIP2017的分数是 $100+0+100+100+0+100$ 所以她还是只能找你帮她做了。。。

给你一个有 $n$ 个点的树，每个点的包括一个位运算 $\operatorname{opt}$ 和一个权值 $x$，位运算有 &,|,^ 三种，分别用 $1,2,3$ 表示。

每次询问包含三个数 $x,y,z$，初始选定一个数 $v$。然后 $v$ 依次经过从 $x$ 到 $y$ 的所有节点，每经过一个点 $i$，$v$ 就变成 $v \operatorname{opt} x_i$。

所以他想问你，最后到 $y$ 时，希望得到的值尽可能大，求最大值？给定的初始值 $v$ 必须是在 $[0,z]$ 之间。

每次修改包含三个数 $x,y,z$，意思是把 $x$ 点的操作修改为 $y$，数值改为 $z$。

输入格式

第一行三个数 $n,m,k$。$k$ 的意义是每个点上的数，以及询问中的数值 $z<2^k$。
之后 $n$ 行每行两个数 $x,y$ 表示该点的位运算编号以及数值。
之后 $n - 1$ 行，每行两个数 $x,y$ 表示 $x$ 和 $y$ 之间有边相连。
之后 $m$ 行，每行四个数，$Q,x,y,z$ 表示这次操作为 $Q$ ($1$ 询问，$2$ 修改)，$x,y,z$ 意义如题所述。

输出格式

对于每个操作 $1$，输出到最后可以造成的最大刺激度 $v$。

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

7
1
5

数据范围与约定

对于 $100\%$ 的数据，$0\le n,m\le 10^5$，$k\le 64$。

题目来源

By 佚名提供