由乃正在做她的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$ 意义如题所述。

输出格式

对于每个操作 $1$，输出到最后可以得到的最大值。

样例数据

样例 1 输入

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

样例 1 输出

7
1
5

样例 2 输入

2 2 2
2 2
2 2
1 2
2 2 2 2
1 2 2 2

样例 2 输出

3

子任务

Idea：f321dd，Solution：f321dd&nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于 $30\%$ 的数据，$n,m\leq 1$。

对于另外 $20\%$ 的数据，$k\leq 5$。

对于另外 $20\%$ 的数据，位运算只会出现一种。

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