#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;
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 (k < w || w > t[ls(k)].w) return find(ls(k), w);
	else 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) {
		if (rs(t[x].fa) == x) 
			res += t[ls(t[x].fa)].siz + 1;
		x = t[x].fa;
	}
	split(rt, res - 1, fx, fy);
	assert(fy == x); rt = merge(fx, fy);
	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), fx, ft);
	split(ft, find(ft, x), ft, fy);
	rt = merge(merge(fx, ft), merge(fz, fy));
}
void insert(int pos) {
	split(rt, pos, 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(rnk(x));
		else if (op == 2) cin >> y, move(x, y);
		else cout << rnk(x) << '\n';
	}
	return 0; 
}