// OBI 2014 - 2nd Stage - Frequencia
// Lúcio Cardoso

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int maxr = 55;

int bit[2][maxr][maxn];

int lastC[maxn], lastL[maxn];
int timeC[maxn], timeL[maxn];

int qtd[maxr];

void upd(int x, int v, int k1, int k2)
{
	for (; x < maxn; x += (x&-x))
		bit[k1][k2][x] += v;
}

int soma(int x, int k1, int k2)
{
	int ans = 0;
	for (; x > 0; x -= (x&-x))
		ans += bit[k1][k2][x];
	return ans;
}

int main(void)
{
	int n, q;
	scanf("%d %d", &n, &q);

	for (int i = 1; i <= n; i++)
	{
		timeL[i] = timeC[i] = i;
		upd(i, 1, 0, 0);
		upd(i, 1, 1, 0);
	}

	for (int i = 1; i <= q; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int x, r;
			scanf("%d %d", &x, &r);

			upd(timeL[x], -1, 0, lastL[x]);

			timeL[x] = i+n+1, lastL[x] = r;
			upd(timeL[x], 1, 0, lastL[x]);
		}
		else if (op == 2)
		{
			int x, r;
			scanf("%d %d", &x, &r);

			upd(timeC[x], -1, 1, lastC[x]);

			timeC[x] = i+n+1, lastC[x] = r;
			upd(timeC[x], 1, 1, lastC[x]);
		}
		else if (op == 3)
		{
			int x;
			scanf("%d", &x);

			memset(qtd, 0, sizeof qtd);

			int tot = 0;
			for (int i = 0; i <= 50; i++)
			{
				qtd[i] += (soma(maxn-1, 1, i)-soma(timeL[x], 1, i));
				tot += qtd[i];
			}

			qtd[lastL[x]] += n-tot;

			int mx = 0, ind = 0;
			for (int i = 50; i >= 0; i--)
				if (qtd[i] > mx)
					mx = qtd[i], ind = i;

			printf("%d\n", ind);
		}
		else
		{
			int x;
			scanf("%d", &x);

			memset(qtd, 0, sizeof qtd);

			int tot = 0;
			for (int i = 0; i <= 50; i++)
			{
				qtd[i] += (soma(maxn-1, 0, i)-soma(timeC[x], 0, i));
				tot += qtd[i];
			}

			qtd[lastC[x]] += n-tot;

			int mx = 0, ind = 0;
			for (int i = 50; i >= 0; i--)
				if (qtd[i] > mx)
					mx = qtd[i], ind = i;

			printf("%d\n", ind);
		}
	}
}