A. Ancient Trees
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Archaeologist Monocarp is exploring some ancient ruins when the heavy stone exit door suddenly slams shut, trapping him inside.

In the center of the ruins, he discovers an ancient artifact shaped like a tree consisting of $$$n$$$ vertices connected by $$$n - 1$$$ magical branches (undirected edges). Each branch contains a glowing magical stone inscribed with an integer weight $$$w$$$.

Monocarp studies the artifact and deduces the ancient rules for traversing its magical pathways. The cost of a simple path between any vertex $$$i$$$ and vertex $$$j$$$, denoted as $$$c(i, j)$$$, is equal to the bitwise XOR of the weights of all edges on the simple path between $$$i$$$ and $$$j$$$. If $$$i = j$$$, the cost is $$$0$$$.

Furthermore, one can travel between two vertices $$$u$$$ and $$$v$$$ using a sequence of intermediate jumps. The total distance $$$d(u, v)$$$ is defined as the minimum possible value of $$$\sum_{i=1}^{k-1} c(a_i, a_{i+1})$$$ over all possible sequences of vertices $$$a_1, a_2, \ldots, a_k$$$ of any length $$$k \ge 1$$$ such that $$$a_1 = u$$$ and $$$a_k = v$$$.

As Monocarp observes the artifact, he realizes the ruins are highly unstable. Occasionally, the magical stones fluctuate and the entire tree changes: a magical surge of value $$$x$$$ occurs, updating the weight of every edge $$$j$$$ to $$$w_j \oplus x$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation).

Desperate to leave, Monocarp finds another ruin near the locked door bearing a cryptic scripture. The scripture indicates that the door will only open if he can correctly answer a series of questions based on the artifact's current state. For a given source vertex $$$s$$$, he must compute the sum of the minimum distances from $$$s$$$ to all vertices $$$i$$$ in the tree, i.e., $$$\sum_{i=1}^n d(s, i)$$$.

You are given $$$q$$$ events (either a magical surge or a query from the scripture). Help Monocarp compute the answers for the scripture to open the door and escape!

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of vertices in the tree artifact and the number of events, respectively.

Each of the next $$$n - 1$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$0 \le w \lt 2^{30}$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$ with an initial weight of $$$w$$$. It is guaranteed that the given edges form a valid tree.

Each of the next $$$q$$$ lines contains a query of one of the following two types:

  • 1 $$$x$$$ ($$$0 \le x \lt 2^{30}$$$): A magical surge occurs, updating the weight of every edge $$$w_j$$$ to $$$w_j \oplus x$$$.
  • 2 $$$s$$$ ($$$1 \le s \le n$$$): The scripture asks for the sum of the minimum distances from the source vertex $$$s$$$ to all vertices $$$i$$$ ($$$1 \le i \le n$$$).
Output

For each query of the second type, print a single integer on a new line — the sum of the minimum distances $$$d(s, i)$$$ for all $$$1 \le i \le n$$$.

Example
Input
4 3
1 2 3
1 3 4
2 4 1
2 1
1 2
2 2
Output
9
11
Note

Explanation for the sample test case:

Initially, the artifact has the following magical branches (edges):

  • Edge $$$(1, 2)$$$ with weight $$$3$$$
  • Edge $$$(1, 3)$$$ with weight $$$4$$$
  • Edge $$$(2, 4)$$$ with weight $$$1$$$

For the first query (2 1), the scripture asks for the sum of distances from source vertex $$$s = 1$$$:

  • $$$d(1, 1) = 0$$$.
  • $$$d(1, 2) = 3$$$.
  • $$$d(1, 3) = 4$$$.
  • $$$d(1, 4)$$$ is the cost of the simple path $$$1 \rightarrow 2 \rightarrow 4$$$. The cost is $$$3 \oplus 1 = 2$$$.
The sum of distances is $$$0 + 3 + 4 + 2 = 9$$$.

In the second query (1 2), a magical surge of $$$x = 2$$$ occurs. All edge weights are updated to $$$w_j \oplus 2$$$:

  • Edge $$$(1, 2)$$$ becomes $$$3 \oplus 2 = 1$$$.
  • Edge $$$(1, 3)$$$ becomes $$$4 \oplus 2 = 6$$$.
  • Edge $$$(2, 4)$$$ becomes $$$1 \oplus 2 = 3$$$.

For the third query (2 2), the scripture asks for the sum of distances from source vertex $$$s = 2$$$ on the updated tree:

  • $$$d(2, 1) = 1$$$.
  • $$$d(2, 2) = 0$$$.
  • $$$d(2, 3)$$$ is the cost of the simple path $$$2 \rightarrow 1 \rightarrow 3$$$. The cost is $$$1 \oplus 6 = 7$$$.
  • $$$d(2, 4) = 3$$$.
The sum of distances is $$$1 + 0 + 7 + 3 = 11$$$.