#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define times(e) for(typeof(e)_=e;_--;)

typedef unsigned long ulong;

char wbuf[1<<25];

struct{
	char const*name;
	int namelen;
	int fixed;
} byr[4001];
int rbyh[1<<16];
ulong b0h,b0b[64];
ulong b1h,b1b[64];
int z0,z1;

int main(){
	char*wp=wbuf;
	rd_init();
	int n=rd();
	int q=rd();
	times(q){
		int t=*rp;
		rp+=2;
		if(t=='1'){
			char const*name=rp;
			int h=0;
			for(int c;c=*rp++,c>=64;){
				h=h*29+c;
			}
			h&=0xffff;
			int namelen=rp-name-1;
			int r=rd();
			rbyh[h]=r;
			byr[r].name=name;
			byr[r].namelen=namelen;
			b0b[r>>6]|=1ul<<(r&63);
			b0h|=1ul<<(r>>6&63);
			z0+=1;
		}
		if(t=='2'){
			int x=rd();
			n-=x;
		}
		if(t=='3'){
			int h=0;
			for(int c;c=*rp++,c>=64;){
				h=h*29+c;
			}
			h&=0xffff;
			int r=rbyh[h];
			if(!byr[r].fixed){
				byr[r].fixed=1;
				if(!(b0b[r>>6]&=~(1ul<<(r&63)))){
					b0h&=~(1ul<<(r>>6&63));
				}
				z0-=1;
				b1b[r>>6]|=1ul<<(r&63);
				b1h|=1ul<<(r>>6&63);
				z1+=1;
			}
			int x=rd();
			n+=x;
		}
		while(z0+z1>n){
			int r;
			int r0=9999;
			if(z0){
				r0=__builtin_ctzl(b0h);
				r0=r0<<6|__builtin_ctzl(b0b[r0]);
			}
			int r1=9999;
			if(z1>n){
				r1=__builtin_ctzl(b1h);
				r1=r1<<6|__builtin_ctzl(b1b[r1]);
			}
			if(r0<r1){
				z0-=1;
				if(!(b0b[r0>>6]&=~(1ul<<(r0&63)))){
					b0h&=~(1ul<<(r0>>6&63));
				}
				r=r0;
			}else{
				z1-=1;
				if(!(b1b[r1>>6]&=~(1ul<<(r1&63)))){
					b1h&=~(1ul<<(r1>>6&63));
				}
				r=r1;
			}
			memcpy(wp,byr[r].name,byr[r].namelen);
			wp+=byr[r].namelen;
			*wp++='\n';
		}
	}
	write(1,wbuf,wp-wbuf);
	_exit(0);
}