#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*
hi, I'm rintaro.
*/
#define g(n,m) get<n>(m)
#define fof(i,o,n) for (ll i = o; i < (ll)n; i++)
#define fof_(i,a) for(auto &i : a)
#define vcin(a) fof_(i,a) cin>>i
#define all(o) o.begin(),o.end()
#define double long double
#define pii pair<ll,ll>
#define vec vector
#define vi vec<ll>
#define vs vec<string>
#define vc vec<char>
#define vvi vec<vi>
#define vpii vec<pii>
#define re return
#define r0 re 0
#define ln(n) cout << n << endl
#define fix(n) << fixed << setprecision(n)
#define out_(n) << n << " "
#define Out cout
#define out(n) << n
#define End << endl
#define imap map<ll,ll>
#define smap map<string,ll>
#define gmap map<ll,vector<ll>>
#define m9 998244353
#define m7 1000000007
#define lny ln("Yes")
#define lnn ln("No")
int main() {
  ll N, Q;
  cin >> N >> Q;
  priority_queue<pair<int,string>,vec<pair<int,string>>,greater<pair<int,string>>> que;
  map<string,bool> mp;
  fof(i,0,Q) {
    ll q;
    cin >> q;
    if(q==1) {
      string s;
      ll r;
      cin >> s >> r;
      mp[s]=false;
      que.push({r,s});
    }
    if(q==2) {
      ll x;
      cin >> x;
      N-=x;
    }
    if(q==3) {
      string s;
      ll x;
      cin >> s >> x;
      mp[s]=true;
      N+=x;
    }
    if((q==1||q==2)&&(ll)que.size()>N) {
      while((ll)que.size()>N) {
        if(mp[que.top().second]==true&&que.top().first<=4000) {
          que.push({que.top().first+5000,que.top().second});
          que.pop();
        }
        else {
          cout << que.top().second << endl;
          que.pop();
        }
      }
    }
  }
}