Description

Yuno is building her OJ. Now she is dealing with the user ranking problem.

There are $n$ users registered on the OJ, numbered $1\sim n$. Initially, they are ranked by their indices. Yuno, depending on her mood, would like to perform the following four types of operations to modify users’ rankings and indices. However, Yuno is in a very bad mood because Deus keeps asking her problems...

Because Deus keeps asking Yuno OI problems, Yuno went to study OI. Since Yuno is quite smart, she learned OI very well.

She entered the provincial team with the first place at RBOI2016 and then won a gold medal and a direct recommendation at NOI2016.

Deus: How do you solve this problem?
Yuno: Isn’t this just an easy problem from NOI2014...
Deus: What if we put it on a tree, with multiple path queries, with modifications?
Yuno: Eh...???
Deus: This problem is called “睡觉困难综合征”~

Although Yuno is good at OI, she basically isn’t good at DS; she can only hand-wave segment trees. For example, her NOI2016 scores were $100+100+100+0+100+100$... and her NOIP2017 scores were $100+0+100+100+0+100$.

So she still has to ask you to help her...

You are given a tree with $n$ nodes. Each node has a bitwise operation $opt$ and a value $x$. The bitwise operations are &, |, ^, represented by $1,2,3$ respectively.

Each query consists of three integers $x,y,z$. You choose an initial number $v$. Then $v$ passes through all nodes on the path from $x$ to $y$ in order. Every time it passes a node $i$, $v$ becomes $v\ opt_i\ x_i$. She wants to know the maximum possible final value when reaching $y$. The initial value $v$ must be in $[0,z]$.

Each modification consists of three integers $x,y,z$, meaning that the operation at node $x$ is changed to $y$ and its value is changed to $z$.

Input Format

The first line contains three integers $n,m,k$. The meaning of $k$ is that each number on a node and each $z$ in the queries are less than $2^k$.

Then $n$ lines follow. Each line contains two integers $x,y$, representing the operation ID and the value of that node.

Then $n-1$ lines follow. Each line contains two integers $x,y$, indicating that there is an edge between $x$ and $y$.

Then $m$ lines follow. Each line contains four integers $Q,x,y,z$. Here $Q$ indicates the type of operation ($1$ for query, $2$ for modification), and $x,y,z$ have the meanings described above.

Output Format

For each operation of type $1$, output the maximum value that can be obtained at the end.

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

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

3

Hint

Idea: f321dd, Solution: f321dd & nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

For $30\%$ of the testdata, $n,m\leq 1$.

For another $20\%$ of the testdata, $k\leq 5$.

For another $20\%$ of the testdata, only one kind of bitwise operation appears.

For $100\%$ of the testdata, $0\leq n,m \leq 10^5$, $0\leq k\leq 64$.

Translated by ChatGPT 5