#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #define _USE_MATH_DEFINES #include #include using namespace std; //#include //using namespace atcoder; #define REP(i,n) for(int i = 0; i < (int)n; i++) #define RREP(i,n) for(int i = (int)n-1; i >= 0; i--) #define LREP(i,n) for(LL i = 0; i < (LL)n; i++) #define Vi vector #define Vl vector #define LP pair #define P pair #define T3 tuple #define T4 tuple #define INF 1000000007 #define SIZE 500010 #define MOD 1000000007 typedef long long LL; int N, Q; int T[SIZE], A[SIZE], B[SIZE], M[SIZE]; Vi E[SIZE], C; int parent[SIZE], s[SIZE]; void init() { REP(i, N + 1) { parent[i] = i; s[i] = 1; } } int par(int a) { if (parent[a] == a) return a; else return parent[a] = par(parent[a]); } int size(int a) { int pa = par(a); return s[pa]; } int merge(int a, int b) { int pa = par(a), pb = par(b); if (pa != pb) { if (size(pa) > size(pb)) swap(pa, pb); parent[pa] = pb; s[pb] += s[pa]; } return pb; } int merge2(int a, int b) { int pa = par(a), pb = par(b); if (pa != pb) { if (pa > pb) swap(pa, pb); parent[pb] = pa; s[pa] += s[pb]; } return pa; } bool same(int a, int b) { int pa = par(a), pb = par(b); if (pa == pb) return true; else return false; } int BIT[SIZE]; void add(int i, int a) { BIT[i] += a; if (i < N) add(i + (i & -i), a); } int sum(int i) { if (i == 0) return 0; return BIT[i] + sum(i - (i & -i)); } int main() { scanf("%d %d", &N, &Q); REP(i, Q) { scanf("%d %d %d", &T[i], &A[i], &B[i]); } init(); REP(i, N) E[i + 1].push_back(i + 1); REP(i, Q) { if (T[i] == 1) { int a = A[i], b = B[i]; if (!same(a, b)) { int pa = par(a), pb = par(b); int p = merge(a, b); if (p != pa) swap(pa, pb); for (auto e : E[pb]) E[pa].push_back(e); E[pb].clear(); } } } REP(i, N) for (auto e : E[i + 1]) C.push_back(e); REP(i, N) M[C[i]] = i + 1; init(); REP(i, Q) { int a = M[A[i]], b = M[B[i]]; if (T[i] == 1) { merge2(a, b); } else if (T[i] == 2) { int left = par(a), right = left + size(a); add(left, B[i]); add(right, -B[i]); } else { cout << sum(a) << endl; } } }