모험가 길드

1부터 $N$까지 번호가 차례대로 매겨진 모험가 길드 $N$개가 있다. 모험가는 길드에 자유롭게 가입하거나 탈퇴할 수 있다. 처음에는 각 길드가 하나씩 동맹을 이루고 있으므로, 동맹은 총 $N$개이다.

길드 $a$와 길드 $b$가 동맹하면, 길드 $a$가 속한 동맹과 길드 $b$가 속한 동맹이 합쳐져 새로운 동맹이 된다. 길드들은 사이가 좋아서 한번 맺은 동맹은 해체되지 않는다.

모험가 길드 본부는 두 길드가 처음으로 같은 동맹에 속하게 될 때마다 이를 기리는 축하 파티를 연다. 축하 파티는 언제든지 열 수 있으며, 같은 두 길드가 파티를 여러 번 열기도 한다. 길드 $a$와 길드 $b$의 축하 파티에는 두 길드가 처음으로 같은 동맹에 속했을 때 그 동맹에 속한 길드들이 참여한다. 예산을 정하려면 파티에 참여할 인원수를 알아야 한다.

그 시점에 동맹에 속한 길드들을 $g_1, g_2, \dots, g_k$라고 하자. $f(g_i)$를 축하 파티를 여는 현재 길드 $g_i$에 속한 인원수라고 할 때, 참여 인원수는 $f(g_1) + f(g_2) + \dots + f(g_k)$이다.

다음 쿼리를 순서대로 처리한다.

• $1$ $i$ $x$: 모험가 길드 $i$에 모험가 $x$명이 가입한다. ($1 \le i \le N$, $1 \le x \le 10^9$)
• $2$ $i$ $x$: 모험가 길드 $i$에서 모험가 $x$명이 탈퇴한다. 모험가 길드 $i$에 모험가 $x$명 이상 있다는 것이 보장된다. ($1 \le i \le N$, $1 \le x \le 10^9$)
• $3$ $a$ $b$: 모험가 길드 $a$와 $b$가 동맹한다. ($1 \le a, b \le N$, $a \ne b$)
• $4$ $a$ $b$: 지금 길드 $a$와 $b$가 축하 파티를 열 때 참여할 인원수를 출력한다. 지금까지 길드 $a$와 $b$가 같은 동맹에 속한 적이 없으면 $-1$을 출력한다. ($1 \le a, b \le N$, $a \ne b$)

첫째 줄에 모험가 길드의 개수 $N$ ($2 \le N \le 300\,000$)과 처리할 쿼리의 개수 $Q$ ($1 \le Q \le 300\,000$)이 주어진다.

둘째 줄에 각 모험가 길드의 초기 인원수 $G_1, G_2, \dots, G_N$이 주어진다. ($1 \le G_i \le 10^9$)

셋째 줄부터 $Q$개의 줄에 위에서 제시한 쿼리가 주어진다.

입력은 모두 정수이다.

4번 쿼리마다 정답을 한 줄에 하나씩 출력한다.