Hyper Tree 문제

$N$개의 정점으로 이루어진 트리가 주어진다. 정점은 $1$번부터 $N$번까지 번호가 붙어 있고, 간선도 입력 순서대로 $1$번부터 $N-1$번까지 번호가 붙어 있다. $i$번 간선의 가중치는 $W_i$이다.

두 가지 유형의 질의가 합해서 $Q$개 주어진다. 2번 질의가 주어질 때마다 답을 출력하라.

• 1 e v: $e$번 간선의 가중치 $W_e$를 $W_e\And v$로 바꾼다. 여기서 $\And$는 Bitwise AND 연산이다.
• 2 n: $\sum_{i=1}^{N}{dist(n, i)}$를 출력한다. $dist(a, b)$는 정점 $a$와 $b$를 잇는 유일한 경로에 있는 간선 가중치를 모두 Bitwise OR 연산한 값이다. $a = b$이면 $dist(a, b) = 0$이다.

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. $(2 \le N \le 300\ 000; 1 \le Q \le 300\ 000)$

다음 $N-1$개의 줄에는 간선 정보 $A_i$, $B_i$, $W_i$가 공백으로 구분되어 주어진다. $i$번 간선은 정점 $A_i$와 $B_i$를 잇고, 초기 가중치는 $W_i$이다. $(1 \le A_i < B_i \le N; 0 \le W_i < 2^{20})$

다음 $Q$개의 줄에는 아래 형식 중 하나로 질의가 주어진다.

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

입력의 모든 수는 정수이고, 2번 질의가 적어도 하나 이상 주어짐이 보장된다.

2번 질의의 결과를 질의가 주어진 순서대로 한 줄에 하나씩 출력한다.