동적 트리 부분 트리 덧셈 및 부분 트리 합

정점이 $N$개인 트리가 주어진다. $i$번째 간선은 정점 $u_i$와 정점 $v_i$를 연결한다. 정점 $i$에는 수 $a_i$가 쓰여 있다.

다음 유형의 쿼리 $Q$개를 순서대로 처리한다:

• 0 $u$ $v$ $w$ $x$: 간선 $(u, v)$를 제거하고 새 간선 $(w, x)$를 추가한다. 처리한 뒤에도 그래프가 트리임이 보장된다.
• 1 $v$ $p$ $x$: 간선 $(v, p)$에 주목하여 $p$를 부모로 간주할 때, 정점 $v$의 부분 트리에 속한 모든 정점의 값에 $x$를 더한다.
• 2 $v$ $p$: 간선 $(v, p)$에 주목하여 $p$를 부모로 간주할 때, 정점 $v$의 부분 트리에 속한 모든 정점의 값의 합을 구한다.

제약 조건

• $2 \le N \le 200000$
• $1 \le Q \le 200000$
• $0 \le a_i \le 10000000$
• $0 \le u_i, v_i < N$
• 그래프는 트리이다
• 유형 0 $u$ $v$ $w$ $x$의 쿼리에 대해:
  • $0 \le u, v, w, x \lt N$
  • 이 유형의 쿼리를 처리할 때 간선 $(u, v)$가 존재한다
  • 처리한 뒤에도 그래프는 트리이다
• 유형 1 $v$ $p$ $x$의 쿼리에 대해:
  • $0 \le v, p \lt N$
  • $0 \le x \le 10000000$
  • 이 유형의 쿼리를 처리할 때 간선 $(v, p)$가 존재한다
• 유형 2 $v$ $p$의 쿼리에 대해:
  • $0 \le v, p \lt N$
  • 이 유형의 쿼리를 처리할 때 간선 $(v, p)$가 존재한다

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$u_0$ $v_0$
$u_1$ $v_1$
$\hspace{11pt} \vdots$
$u_{N - 2}$ $v_{N - 2}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\hspace{14pt} \vdots$
$\mathrm{Query}_{Q - 1}$

문제에서 요구한 값을 출력한다.