由乃的OJ ### 题目描述 由乃正在做她的OJ。现在她在处理OJ上的用户排名问题。 OJ 上注册了 $n$ 个用户，编号为 $1\sim 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$ 个点的树，每个点的包括一个位运算 $opt$ 和一个权值 $x$，位运算有`&`，`|`，`^` 三种，分别用 $1,2,3$ 表示。 每次询问包含三个整数 $x,y,z$，初始选定一个数 $v$。然后 $v$ 依次经过从 $x$ 到 $y$ 的所有节点，每经过一个点 $i$，$v$ 就变成 $v\ opt_i\ 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$ 意义如题所述。 其中，$0\leq n,m \leq 10^5$，$0\leq k\leq 64$。 ### 输出描述 对于每个操作 $1$，输出到最后可以得到的最大值。 ### 输入输出样例 #### 示例 1 >输入 ```txt 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 ``` >输出 ```txt 7 1 5 ```