F. Good Tree Queries
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar gave a weighted tree initially containing $$$n$$$ nodes to Naveen and Pavan Kalyan in 2023. Almost a year has completed, so he came up with $$$3$$$ types of queries to test their knowledge on trees.

Before asking about queries, Yugandhar came up with an infinite integer array $$$A$$$ defined as $$$(A_0 = 1, A_{n} = A_{n-1}+4)$$$ and an infinite binary array $$$B$$$ defined as $$$(B_0 = 0, B_{2n} = B_{n}, B_{2n+1} = 1-B_{n})$$$. And also he gave one empty array to Naveen and one empty array to Pavan Kalyan and called them as Naveen's array and Pavan kalyan's array respectively.

Later he splits each element of $$$A_i (i \ge 0)$$$ to Naveen's array and Pavan Kalyan's array in the following way:

  1. If $$$B_i=0$$$, then he will append $$$⌊\frac{A_i}{2}⌋$$$ to Naveen's array and $$$⌊\frac{A_i}{2}⌋+1$$$ to Pavan Kalyan's array.
  2. If $$$B_i=1$$$, then he will append $$$⌊\frac{A_i}{2}⌋$$$ to Pavan Kalyan's array and $$$⌊\frac{A_i}{2}⌋+1$$$ to Naveen's array.

After splitting, he will ask the following type of queries to both:

  1. 1 x y w — He asked Naveen and Pavan Kalyan to add an edge between $$$x$$$ and $$$y$$$ with weight $$$w$$$ (note that after this query it is guaranteed that the graph is a tree).One of the $$$x$$$ and $$$y$$$ is already present in the tree and another is the new node, i.e., after this operation the size of the given tree will increase by $$$1$$$.
  2. 2 0 — He asked Naveen to find the number of simple paths whose bitwise XOR of their edges has to be in his array (note that the path between $$$(x,y)$$$ is different from $$$(y,x)$$$ ).
  3. 2 1 — He asked Pavan Kalyan to find the number of simple paths whose bitwise XOR of their edges has to be in his array (note that the path between $$$(x,y)$$$ is different from $$$(y,x)$$$ ).

Note that the given tree is guaranteed that there is atmost $$$1$$$ edge between two nodes.

Unfortunately, both Naveen and Pavan Kalyan didn't learn much about trees, so please help them by telling answers to the $$$2^{nd}$$$ and $$$3^{rd}$$$ type queries.

Input

The first line of each test contains two integers $$$n,q$$$ $$$(1 \le n,q \le 10^6)$$$ — initial number of nodes in the tree and number of queries.

The next $$$n-1$$$ lines contain three integers $$$x,y,w$$$ $$$(1 \le x,y \le n, x≠y, 1 \le w \le 10^9)$$$ — there is an edge between $$$x$$$ and $$$y$$$ with weight $$$w$$$.

The following $$$q$$$ lines can fall into three cases:

  • The first type of query: The $$$i^{th}$$$ line contains — 1 x y w $$$(1 \le w \le 10^9)$$$ Ensure that one node is an unseen node and is the smallest numbered.
  • The second type of query: The $$$i^{th}$$$ line contains — 2 0
  • The third type of query: The $$$i^{th}$$$ line contains — 2 1

Queries description was mentioned in the problem statement.

Output

For each test, print the required answer for the $$$2^{nd}$$$ and $$$3^{rd}$$$ type queries respectively.

Example
Input
5 5
1 2 2
1 5 2
2 3 2
2 4 2
2 0
2 1
1 5 6 2
2 0
2 1
Output
8
12
14
16