Hyper Tree Problem

The tree has $N$ vertices numbered from $1$ to $N$, and its $N-1$ edges are numbered from $1$ to $N-1$ in input order. Edge $i$ has weight $W_i$.

A total of $Q$ queries of two types are given. For each query of type 2, print the answer.

• 1 e v: Change the weight $W_e$ of edge $e$ to $W_e\And v$. Here $\And$ is the Bitwise AND operation.
• 2 n: Print $\sum_{i=1}^{N}{dist(n, i)}$. $dist(a, b)$ is the Bitwise OR of all edge weights on the unique path between vertices $a$ and $b$. If $a = b$, then $dist(a, b) = 0$.

The first line contains $N$ and $Q$, separated by a space. $(2 \le N \le 300\ 000; 1 \le Q \le 300\ 000)$

Each of the next $N-1$ lines contains $A_i$, $B_i$, and $W_i$, separated by spaces. Edge $i$ connects vertices $A_i$ and $B_i$, and its initial weight is $W_i$. $(1 \le A_i < B_i \le N; 0 \le W_i < 2^{20})$

Each of the next $Q$ lines is one of the following queries.

• 1 e v: $(1 \le e < N; 0 \le v < 2^{20})$
• 2 n: $(1 \le n \le N)$

All numbers in the input are integers. At least one query of type 2 is guaranteed.

For each query of type 2, print the result on its own line, in the order the queries are given.