#line 1 "A.cpp" #include using namespace std; using ll = long long; #define endl "\n" void print(){ cout << '\n'; } template void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << ' '; print(forward(tail)...); } template void print(vector &A){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << ' '; } } template void prisep(vector &A, S sep){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << sep; } } template void print(vector> &A){ for(auto &row: A) print(row); } #line 3 "Library/C++/data_structure/WeightedUnionFind.hpp" using namespace std; template struct WeightedUnionFind{ int n; vector par; vector D; vector W; int group; WeightedUnionFind(int n, vector W) : n(n), W(W){ par.assign(n, -1); group = n; D.assign(n, T(0)); } WeightedUnionFind(int n): WeightedUnionFind(n, vector(n, T(0))) {} int find(int x){ if(par[x] < 0) return x; int p = find(par[x]); D[x] += D[par[x]]; par[x] = find(p); return p; } bool unite(int x, int y, T d){ // x = y + d int xp = find(x); int yp = find(y); d -= D[x]; x = xp; d += D[y]; y = yp; if(x == y){ assert(d == 0); return false; } if(par[x] > par[y]){ swap(x, y); d *= -1; } group--; par[x] += par[y]; D[y] = -d; par[y] = x; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -par[find(x)]; } vector roots(){ vector ret; for(int i = 0; i < n; i++){ if(i == find(i)) ret.push_back(i); } return ret; } T diff(int x, int y){ assert(same(x, y)); return D[x] - D[y]; } void all_add(int a, T b){ a = find(a); W[a] += b; } T get(int a){ int p = find(a); return W[p] + diff(a, p); } }; #line 43 "A.cpp" void solve(){ int n, Q; cin >> n >> Q; int t, a, b; WeightedUnionFind UF(n); while(Q--){ cin >> t >> a >> b; a--; if(t == 1){ b--; UF.unite(a, b, UF.get(a) - UF.get(b)); } else if(t == 2){ UF.all_add(a, b); } else{ print(UF.get(a)); } } } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); return 0; }