Adventurer Guilds

Adventurer guilds numbered $1$ to $N$ exist. An adventurer can join or leave a guild freely. At the start, each guild forms its own alliance, so there are $N$ alliances in total.

When guild $a$ and guild $b$ form an alliance, the alliance containing $a$ and the alliance containing $b$ merge into one new alliance. The guilds get along well, so an alliance is never dissolved.

The guild headquarters holds a celebration party each time two guilds first end up in the same alliance. A party can be held at any time, and the same pair of guilds may hold several parties. The party for guilds $a$ and $b$ includes all guilds in the alliance that contains both of them at the moment they first share an alliance. The headquarters needs to know how many people attend each party to plan the budget.

Suppose the guilds in that alliance at that moment are $g_1, g_2, \dots, g_k$. Let $f(g_i)$ be the number of adventurers in guild $g_i$ at the time the party is held. The number of attendees is $f(g_1) + f(g_2) + \dots + f(g_k)$.

Process the following queries in order.

• $1$ $i$ $x$: $x$ adventurers join guild $i$. ($1 \le i \le N$, $1 \le x \le 10^9$)
• $2$ $i$ $x$: $x$ adventurers leave guild $i$. Guild $i$ is guaranteed to have at least $x$ adventurers. ($1 \le i \le N$, $1 \le x \le 10^9$)
• $3$ $a$ $b$: guilds $a$ and $b$ form an alliance. ($1 \le a, b \le N$, $a \ne b$)
• $4$ $a$ $b$: print the number of attendees if guilds $a$ and $b$ held a party now. If guilds $a$ and $b$have never been in the same alliance, print $-1$. ($1 \le a, b \le N$, $a \ne b$)

The first line contains the number of guilds $N$ ($2 \le N \le 300\,000$) and the number of queries $Q$ ($1 \le Q \le 300\,000$).

The second line contains the initial number of adventurers in each guild, $G_1, G_2, \dots, G_N$. ($1 \le G_i \le 10^9$)

The next $Q$ lines each contain one query as described above.

All input values are integers.

For each query of type $4$, print the answer on its own line.