Problem Description

Yuno is working on her Online Judge (OJ). Currently, she is dealing with the user ranking issue on the OJ.

The OJ has registered $n$ users, numbered from $1$ to $n$, initially ranked by their numbers. Yuno will perform one of the following four operations based on her mood to modify the users' rankings and numbers. However, Yuno is in a very bad mood because Deus keeps asking her questions.

Since Deus keeps asking Yuno about OI problems, she decided to learn OI. Due to her high intelligence, she mastered OI very well. She entered the provincial team with the first place in RBOI2016 and won a gold medal at NOI2016, securing a direct admission.

Deus: How do I solve this problem?
Yuno: Isn't this a simple problem from NOI2014?
Deus: What if it's on a tree, with multiple chain queries and modifications?
Yuno: Uh...?
Deus: This problem is called "Difficult Syndrome to Sleep"~

Although Yuno is good at OI, she is not proficient in Data Structures (DS), barely able to conceptualize segment trees. For example, her scores at NOI2016 were $100+100+100+0+100+100$... and at NOIP2017 were $100+0+100+100+0+100$.

Therefore, she still has to ask you for help...

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

Each query contains three integers $x, y, z$. You start with an initial number $v$. Then $v$ passes through all nodes from $x$ to $y$. Each time $v$ passes through a node $i$, $v$ becomes $v\ opt_i\ x_i$. Yuno wants to know the maximum value that can be obtained at $y$ after passing through all nodes from $x$ to $y$, given that the initial value $v$ must be within $[0, z]$.

Each modification contains three integers $x, y, z$, meaning to change the operation of node $x$ to $y$ and the value to $z$.

Input Format

The first line contains three integers $n, m, k$. $k$ represents that the numbers at each node and the value $z$ in the queries are less than $2^k$.

The next $n$ lines, each contains two integers $x, y$ representing the bitwise operation number and the value of the node.

The next $n - 1$ lines, each contains two integers $x, y$ indicating that there is an edge between $x$ and $y$.

The next $m$ lines, each contains four integers $Q, x, y, z$ indicating the operation type $Q$ ($1$ for query, $2$ for modification), and $x, y, z$ as described in the problem.

Output Format

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

Sample Input and Output

Input Sample #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

Output Sample #1

7
1
5

Input Sample #2

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

Output Sample #2

3

Notes/Hints

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

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

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

For another $20\%$ of the data, only one type of bitwise operation will be used.

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

见题面 Input 部分

见题面 Output 部分