#pragma GCC target ("avx2") #pragma GCC optimize ("Ofast") #include #include #include #include /* namespace niu { struct fastin { static const int bufsize = 1 << 24; char buf[bufsize]; char* iter; fastin() { iter = buf; for(int t = 0, k; (k = read(STDIN_FILENO, buf + t, sizeof(buf)) - t) > 0; t += k); } fastin& operator>>(int& num) { num = 0; bool neg = false; while(*iter < '+') iter++; if(*iter == '-') { neg = true; iter++; } else if(*iter == '+') iter++; while(*iter >= '0') num = 10 * num + *(iter++) - '0'; if(neg) num = -num; return *this; } } fin; struct fastout { static const int bufsize = 1 << 24; char buf[bufsize]; char* iter; fastout() { iter = buf; } ~fastout() { for(int t = 0, k; (k = write(STDOUT_FILENO, buf + t, iter - buf - t)) > 0; t += k); } fastout& operator<<(int num) { static char tmp[20]; if(num == 0) { *(iter++) = '0'; return *this; } if(num < 0) { *(iter++) = '-'; num = -num; } int i = 0; while(num) { tmp[i++] = num % 10; num /= 10; } while(i--) { *(iter++) = tmp[i] + '0'; } return *this; } fastout& operator<<(char c) { *(iter++) = c; return *this; } } fout; } */ #include namespace niu { char cur; struct FIN { static inline bool is_blank(char c) { return c <= ' '; } inline char next() { return cur = getc_unlocked(stdin); } inline char peek() { return cur; } inline void skip() { while(is_blank(next())){} } #define intin(inttype) \ FIN& operator>>(inttype& n) { \ bool sign = 0; \ n = 0; \ skip(); \ while(!is_blank(peek())) { \ if(peek() == '-') sign = 1; \ else n = (n << 1) + (n << 3) + (peek() & 0b1111); \ next(); \ } \ if(sign) n = -n; \ return *this; \ } intin(int) intin(long long) } fin; char tmp[128]; struct FOUT { static inline bool is_blank(char c) { return c <= ' '; } inline void push(char c) { putc_unlocked(c, stdout); } FOUT& operator<<(char c) { push(c); return *this; } FOUT& operator<<(const char* s) { while(*s) push(*s++); return *this; } #define intout(inttype) \ FOUT& operator<<(inttype n) { \ if(n) { \ char* p = tmp + 127; bool neg = 0; \ if(n < 0) neg = 1, n = -n; \ while(n) *--p = (n % 10) | 0b00110000, n /= 10; \ if(neg) *--p = '-'; \ return (*this) << p; \ } \ else { \ push('0'); \ return *this; \ } \ } intout(int) intout(long long) } fout; } struct union_find { std::vector par; std::vector Sigma; union_find(int N): par(N, -1) , Sigma(N, 0) { } int root(int x) { if(par[x] < 0) { return x; } int v = x; while(par[par[v]] >= 0) { v = par[v]; Sigma[x] += Sigma[v]; } par[x] = par[v]; return par[v]; } void unite(int x, int y) { x = root(x); y = root(y); if(x == y) return; if(par[x] > par[y]) std::swap(x, y); par[x] += par[y]; par[y] = x; Sigma[y] -= Sigma[x]; return; } void add(int v, int a) { Sigma[root(v)] += a; } int value(int v) { int r = root(v); if(r == v) { return Sigma[v]; } else { return Sigma[v] + Sigma[r]; } } }; #include using namespace std; using i64 = long long; #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) #define all(x) x.begin(),x.end() int main() { int N, Q; niu::fin >> N >> Q; union_find uf(N); while(Q--) { int t, a, b; niu::fin >> t >> a >> b; a--; if(t == 1) { b--; uf.unite(a, b); } else if(t == 2) { uf.add(a, b); } else { niu::fout << uf.value(a) << '\n'; } /* cout << Q << endl; rep(i,0,N) { cout << i << " = " << uf.Sigma[i] << " " << uf.par[i] << endl; }*/ } }