25538번 - 모험가 길드

$1 \dots N$까지 번호가 차례대로 매겨진 모험가 길드 $N$개가 있다. 모험가 길드에는 모험가들이 자유롭게 가입하거나 탈퇴할 수 있다. 처음에는 각각의 길드마다 하나의 동맹이 존재하여, 총 $N$개의 동맹이 존재한다.

모험가 길드들은 서로 동맹할 수 있다. 길드 $a$와 길드 $b$가 동맹하면, 길드 $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 ≤ i ≤ N, 1 ≤ x ≤ 10^9)$
• $2$ $i$ $x$ : 모험가 길드 $i$에서 모험가 $x$명이 탈퇴한다. 모험가 길드 $i$에 모험가 $x$명 이상 있다는 것이 보장된다. $(1 ≤ i ≤ N, 1 ≤ x ≤ 10^9)$
• $3$ $a$ $b$ : 모험가 길드 $a$와 $b$가 동맹한다. $(1 ≤ a, b ≤ N, a ≠ b)$
• $4$ $a$ $b$ : 모험가 길드 $a$와 $b$가 축하 파티를 개최할 때 참여할 인원수를 출력한다. 만약 지금까지 길드 $a$와 $b$가 같은 동맹에 속한 적이 없었으면 $-1$을 출력한다. $(1 ≤ a, b ≤ N, a ≠ b)$

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

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

셋째 줄부터 $Q$개의 줄에 문제에서 제시된 쿼리들이 주어진다.

주어지는 입력은 모두 정수이다.

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