#include<bits/stdc++.h> #define N 150005 usingnamespacestd;
inlineintread(){ int x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); return x * f; }
namespace LCT{ int Fa[N], fa[N], ch[N][2], sum[N], val[N], tag[N]; intfind(int x){ return Fa[x] == x ? x : Fa[x] = find(Fa[x]); } inlineboolisroot(int x){ return ch[fa[x]][0] != x && ch[fa[x]][1] != x; } inlinevoidpushup(int x){ sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x]; } inlinevoidrev(int x){ swap(ch[x][0], ch[x][1]); tag[x] ^= 1; } inlinevoidpushdown(int x){ if (!tag[x]) return; tag[x] = 0; if (ch[x][0]) rev(ch[x][0]); if (ch[x][1]) rev(ch[x][1]); } inlinevoidrotate(int x){ int y = fa[x], z = fa[y], k = (ch[y][1]==x); if (!isroot(y)) ch[z][ch[z][1]==y] = x; fa[x] = z; ch[y][k] = ch[x][!k]; fa[ch[x][!k]] = y; ch[x][!k] = y; fa[y] = x; pushup(y); pushup(x); } int stk[N], top; inlinevoidsplay(int x){ stk[top=1] = x; for (int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i]; while (top) pushdown(stk[top--]); while (!isroot(x)) { int y = fa[x], z = fa[y]; if (!isroot(y)) ((ch[y][1]==x)^(ch[z][1]==y)) ? rotate(x) : rotate(y); rotate(x); } } inlinevoidaccess(int x){ for (int i = 0; x; i = x, x = find(fa[x])) { splay(x); ch[x][1] = i; if (i) fa[i] = x; pushup(x); } } inlinevoidmakeroot(int x){ access(x); splay(x); rev(x); } inlinevoidsplit(int x, int y){ makeroot(x); access(y); splay(y); } inlinevoidlink(int x, int y){ makeroot(x); fa[x] = y; } queue<int> q; inlinevoidmerge(int x, int y){ split(x, y); q.push(y); while (!q.empty()) { int u = q.front(); q.pop(); Fa[find(u)] = y; if (ch[u][0]) q.push(ch[u][0]); if (ch[u][1]) q.push(ch[u][1]); ch[u][0] = ch[u][1] = 0; } val[y] = sum[y]; } }
int n, m, Fa[N], a[N];
intfind(int x){ return Fa[x] == x ? x : Fa[x] = find(Fa[x]); } voidLink(int x, int y){ int fx = LCT::find(x), fy = LCT::find(y); if (fx == fy) return; int u = find(x), v = find(y); if (u != v) { Fa[u] = v; LCT::link(fx, fy); } else { LCT::merge(fx, fy); } }
intmain(){ n = read(), m = read(); for (int i = 1; i <= n; i++) a[i] = LCT::val[i] = read(); for (int i = 1; i <= n; i++) Fa[i] = LCT::Fa[i] = i; for (int i = 1, tp, x, y; i <= m; i++) { tp = read(); x = read(); y = read(); if (tp == 1) { Link(x, y); } elseif (tp == 2) { int v = y - a[x]; a[x] = y; int fx = LCT::find(x); LCT::makeroot(fx); LCT::val[fx] += v; LCT::pushup(fx); } else { if (find(x) != find(y)) puts("-1"); else { int fx = LCT::find(x), fy = LCT::find(y); LCT::split(fx, fy); printf("%d\n", LCT::sum[fy]); } } } return0; }