동적 그래프 정점 가산 연결 요소 합

$N$개의 정점을 가진 빈 그래프가 주어진다. $i$번째 정점에는 값 $a_i$가 적혀 있다.

$Q$개의 쿼리를 처리한다.

• 0 $u$ $v$ : 정점 $u$와 정점 $v$ 사이에 간선을 추가한다. (이 쿼리의 직전에 정점 $u$와 정점 $v$ 사이에 간선이 없음이 보장된다.)
• 1 $u$ $v$ : 정점 $u$와 정점 $v$ 사이의 간선을 제거한다. (이 쿼리의 직전에 정점 $u$와 정점 $v$ 사이에 간선이 있음이 보장된다.)
• 2 $v$ $x$ : $a_v \gets a_v + x$
• 3 $v$ : 경로를 통해 정점 $v$와 연결된 모든 정점에 적힌 값의 합을 출력한다.

제약 조건

• $1 \leq N, Q \leq 300000$
• $0 \leq a_i, x \leq 1000000000$
• $0 \leq u_i, v_i < N$
• $u_i \neq v_i$

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

3 $v$ : 경로를 통해 정점 $v$와 연결된 모든 정점에 적힌 값의 합을 출력한다.