题目背景

Zzz……，Zzz……

问题描述

一棵 \(n\) 个节点的树，每个节点上有一个位运算操作符(与、或、异或，分别用 \(1,2,3\) 表示)和一个数字，走过一个点的时候当前值就会和这个数字做相应运算。现在给定 \(x,y,z\)，要求在 \([0,z]\) 中选区一个初值使从 \(x\) 点走到 \(y\) 点的最终结果最大。支持动态修改点上的操作符与数字。

输入格式

第一行三个数 \(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\) 意义如题所述。若为修改，给三个数 \(x，y，z\)，意思是把 \(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

数据范围

对于 \(30\%\) 的数据，\(n，m \le 1000\)

对于另外 \(20\%\) 的数据，\(k \le 5\)

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

对于 \(100\%\) 的数据，\(0 \le n,m \le 100000 , k \le 64\)

时空限制

\(2\mathrm s,512\mathrm{MiB}\)