Yuno is working on her OJ. She is currently dealing with the user ranking system on the OJ.

There are $n$ registered users on the OJ, numbered $1$ to $n$, initially ranked by their ID. Yuno performs four types of operations on these users based on her mood, modifying their rankings and IDs. However, Yuno is in a very bad mood because Deus asks her questions every day...

Because Deus asks Yuno OI questions every day, Yuno went to study OI. Since Yuno is quite intelligent, she became very proficient in OI.

She entered the provincial team with first place in RBOI2016 and won a gold medal in NOI2016, securing a recommendation for university admission.

Deus: How do you solve this problem? Yuno: Isn't this just a trivial problem from NOI2014... Deus: What if it were on a tree, with multiple chain queries and updates? Yuno: Eh...??? Deus: This problem is called "Sleep Deprivation Syndrome"~

Although Yuno is good at OI, she basically doesn't know data structures and can only talk about segment trees theoretically. For example, her scores in NOI2016 were $100+100+100+0+100+100$... and her scores in NOIP2017 were $100+0+100+100+0+100$.

So, she has to ask you to help her solve it...

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

Each query consists of three integers $x, y, z$. Initially, a value $v$ is chosen. Then $v$ passes through all nodes on the path from $x$ to $y$ in order. Every time it passes through a node $i$, $v$ becomes $v\ opt_i\ x_i$. You want to find the maximum possible value at the end of the path at $y$, given that the initial value $v$ must be in the range $[0, z]$.

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

Input

The first line contains three integers $n, m, k$. $k$ means that the numbers on each node, as well as the value $z$ in the queries, are all less than $2^k$.

The next $n$ lines each contain two integers $x, y$ representing the bitwise operation ID and the value for that node.

The next $n - 1$ lines each contain two integers $x, y$ representing an edge between $x$ and $y$.

The next $m$ lines each contain four integers $Q, x, y, z$, where $Q$ is the operation type ($1$ for query, $2$ for update), and $x, y, z$ have the meanings described above.

Output

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

Examples

Input 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 1

7
1
5

Input 2

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

Output 2

3

Subtasks

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 appears.

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