#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 3e5 + 5;
struct node {
	int ls, rs, rd, siz, fa, w;
} t[N];
#define ls(k) t[k].ls
#define rs(k) t[k].rs
void pushup(int k) {
	t[k].siz = t[ls(k)].siz + t[rs(k)].siz + 1;
	if (ls(k)) t[ls(k)].fa = k; 
	if (rs(k)) t[rs(k)].fa = k;
	t[k].w = min({t[ls(k)].w, t[rs(k)].w, k});
//	assert(t[k].w);
}
void split(int k, int w, int &x, int &y) {
	if (!k) return x = y = 0, void();
	if (t[ls(k)].siz >= w) y = k, split(ls(k), w, x, ls(y)), pushup(y);
	else x = k, split(rs(k), w - t[ls(k)].siz - 1, rs(x), y), pushup(x);
}
int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (t[x].rd > t[y].rd) return rs(x) = merge(rs(x), y), pushup(x), x;
	else return ls(y) = merge(x, ls(y)), pushup(y), y;
} 
int ts, rt, fx, fy, fz, ft, fu, fv;
mt19937 Rand(2347); 
int newnode() {
	return ts++, t[ts] = {0, 0, Rand(), 1, 0, ts}, ts;
}
int find(int k, int w) {
    if (!k) return 0;
    if (w > t[ls(k)].w || w > k) return find(ls(k), w);
    return t[ls(k)].siz + 1 + find(rs(k), w);
}
int rnk(int x) {
	if (!x) return 0;
    int res = t[ls(x)].siz + 1;
    while (x != rt) {
        if (p[p[x].fa].rs == x) 
			res += p[ls(p[x].fa)].siz + 1;
        x = p[x].fa;
    }
    return res;
}
void move(int x, int y) {
	split(rt, rnk(x) - 1, fx, fz);
    split(fz, find(fz, x), fz, fy);
    rt = merge(fx, fy);
    split(rt, rnk(y), ft, fu);
    split(fu, find(fu, x), fu, fv);
    rt = merge(merge(ft, fu), merge(fz, fv));
}
void insert(int x) {
	split(rt, rnk(x), fx, fy);
	rt = merge(merge(fx, newnode()), fy);
} 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int sub, n; cin >> sub >> n; t[0].w = N;
	while (n--) {
		int op, x, y; cin >> op >> x; 
		if (op == 1) insert(x);
		else if (op == 2) cin >> y, move(x, y);
		else cout << rnk(x) << '\n';
	}
	return 0; 
} 

answer.code: In function ‘int newnode()’:
answer.code:30:41: warning: narrowing conversion of ‘Rand.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()’ from ‘std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   30 |         return ts++, t[ts] = {0, 0, Rand(), 1, 0, ts}, ts;
      |                                     ~~~~^~
answer.code: In function ‘int rnk(int)’:
answer.code:41:13: error: ‘p’ was not declared in this scope
   41 |         if (p[p[x].fa].rs == x)
      |             ^
answer.code:43:13: error: ‘p’ was not declared in this scope
   43 |         x = p[x].fa;
      |             ^