F. Forest of Magic
time limit per test
8 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Forest of Magic, as its name suggests, is a forest full of magic. In the Forest lives Kirisame Marisa, who is a young but skilled magician.

There are many places in the Forest, and they are connected with bidirectional roads, in such way that each pair of places are connected directly or indirectly by the roads, and there is only one simple path from a place to the other one. In other words, the places and the roads in the Forest forms a tree.

Initially, there are $$$n$$$ places in the Forest, numbered from $$$1$$$ to $$$n$$$. Marisa's house is in $$$1$$$, so the Forest can be regarded as a tree rooted on $$$1$$$ from Marisa's point of view.

As all lost things will go into Gensokyo, there will be new places now and then, and the new places will also have exactly one bidirectional road connecting with an existing place, so that the Forest is still a tree after the new place appears.

There are many naughty fairies in the Forest too. Sometimes a fairy will go from a specific place to another place, and since fairies are nature incarnate, on each place passed by the fairy, $$$k$$$ flowers with a specific color will grow out. The colors can be denoted as numbers from $$$1$$$ to $$$10^9$$$.

Marisa likes flowers, and sometimes she wants to invite her friends to watch the flowers together. Before that, she will count the total number of the flowers with color number no greater than $$$c$$$, in the subtree of a specific place. We say a place $$$v$$$ is in the subtree of $$$u$$$ if $$$u$$$ lies on the simple path between $$$v$$$ and $$$1$$$. Note that Marisa will not pick the flowers, so the counting will not change anything.

However, the Forest is too big, so she asks you to count the flowers each time instead. Also, you must answer her immediately each time she makes a query.

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 3 \times 10^4$$$, $$$0 \le q \le 10^5$$$), indicating there are $$$n$$$ places in the Forest initially, and Marisa will give you $$$q$$$ operations.

In each of the following $$$n-1$$$ lines, there are two positive integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) separated by a single space, indicating that there is a bidirectional road connecting the $$$u_i$$$-th and the $$$v_i$$$-th place directly.

Each of the following $$$q$$$ lines represents an operation by order, which has one of the three formats below:

  • $$$1\;u_i$$$: A new place appears, and it is numbered $$$n' + 1$$$, where $$$n'$$$ denotes the count of places before this operation. In addition, there is a road connecting the new place and the $$$u_i$$$-th ($$$1 \le u_i \le n'$$$) place.
  • $$$2\;u_i\;v_i\;c_i\;k_i$$$: A fairy goes from the $$$u_i$$$-th place to the $$$v_i$$$-th place, and there will grow up $$$k_i$$$ ($$$1 \le k_i \le 10^7$$$) flowers of color $$$c_i$$$ ($$$1 \le c_i \le 10^9$$$) on each place on the only simple path between them, including both endpoints. It is guaranteed that the $$$u_i$$$-th and the $$$v_i$$$-th place exist.
  • $$$3\;u_i\;c_i$$$: Marisa wants to know that, how many flowers are in the subtree of the $$$u_i$$$-th place, whose color numbers are no greater than $$$c_i$$$ ($$$1 \le c_i \le 10^9$$$). The definition of the subtree of a place is mentioned above in the statement.

In addition, to make sure that you answers Marisa immediately each time, you need to keep a variable $$$\mathrm{last}$$$, which equals to the value of the last answer modulo $$$2^{31}$$$ (or $$$0$$$ initially). Each time you read a line of operation, all numbers except the first one should bitwise XOR to $$$\mathrm{last}$$$, and the result is the actual value of that number.

The bitwise XOR of non-negative integers $$$A$$$ and $$$B$$$, $$$A \oplus B$$$, is defined as follows:

  • When $$$A \oplus B$$$ is written in base two, the digit in the $$$2^k$$$'s place ($$$k \geq 0$$$) is $$$1$$$ if exactly one of the digits in that place of $$$A$$$ and $$$B$$$ is $$$1$$$, and $$$0$$$ otherwise.
It is guaranteed that:
  • Every number in input is a non-negative integer less than $$$2^{31}$$$.
  • After recovering using the above method, the actual values of the numbers meet the restrictions above.
  • The total number of places will not exceed $$$5 \times 10^4$$$.
  • The total count of the second type of operation will not exceed $$$5 \times 10^4$$$.
Output

For each operation of the third type, print a non-negative integer in a single line, denoting the count of flowers in the subtree of the $$$u_i$$$, which color is no greater than $$$c_i$$$.

Example
Input
3 5
1 2
1 3
2 2 3 1 4
3 1 1
1 13
2 13 8 14 13
3 13 14
Output
12
14
Note

The actural value of the numbers in the input should be:

3 5

1 2

1 3

2 2 3 1 4

3 1 1

1 1

2 1 4 2 1

3 1 2