#include<bits/stdc++.h>
using namespace std;
bool isok(string &s){
	for(auto c:s){
		if('a' > c || 'z' < c) return false;
	}
	return true;
}
int main(){
	int n, q;
	cin >> n >> q;
	assert(1 <= n && n <= 100);
	assert(1 <= q && q <= 100000);
	set<string> sv;
	set<pair<int, string>> s1, s2;
	map<string, int> rt;
	while(q--){
		int t;
		cin >> t;
		assert(1 <= t && t <= 3);
		if(t == 1){
			string s;
			int r;
			cin >> s >> r;
			assert(isok(s));
			assert(1 <= (int)s.size() && (int)s.size() <= 100);
			assert(0 <= r && r <= 4000);
			s2.insert({r, s});
			rt[s] = r;
			assert(!sv.count(s));
			sv.insert(s);
		}else if(t == 2){
			int x;
			cin >> x;
			assert(1 <= x && x <= 10);
			n -= x;
		}else if(t == 3){
			string s;
			int x;
			cin >> s >> x;
			assert(isok(s));
			assert(1 <= (int)s.size() && (int)s.size() <= 100);
			assert(1 <= x && x <= 10);
			n += x;
			assert(rt.count(s));
			int r = rt[s];
			s2.erase({r, s});
			s1.insert({r, s});
		}
		vector<pair<int, string>> ans;
		while((int)s2.size() + (int)s1.size() > n){
			if((int)s2.size() > 0){
				auto [p, q] = *s2.begin();
				s2.erase({p, q});
				rt.erase(q);
				ans.push_back({p, q});
			}else{
				auto [p, q] = *s1.begin();
				s1.erase({p, q});
				rt.erase(q);
				ans.push_back({p, q});
			}
		}
		sort(ans.begin(), ans.end());
		for(auto s:ans) cout << s.second << '\n';
	}
	assert((int)sv.size() <= 100);
}