#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;

const int INF = 1e9;
using ll = long long;
using ull = unsigned long long;
using ullv = vector<ull>;
using inv = vector<int>;
using stv = vector<string>;
using llv = vector<ll>;
using ld = long double;
using pint = pair<int,int>;
#define FOR(i,l,r) for(int i=(int)(l); i<(int)(r); i++)
#define rep(i,r) for(ll i=0; i<(ll)(r); i++)
#define repl(i,r) for(long long i=0; i<(long long)(r); i++)
#define FORl(i,l,r) for(long long i=(long long)(l); i<(long long)(r); i++)
#define INFL (long long)((1LL<<62)-(1LL<<31))
#define pb(x) push_back(x)
#define printVec(x) for(auto s:x) cout << s << " "; cout << endl
#define ALL(x) x.begin(),x.end()

template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
ll floor(ll N, ll d){
    if(d < 0)
        N *= -1, d *= -1;
    
    if(N > 0)
        return N / d;
    else
        return (N+1) / d-1;
}
ll ceil(ll N, ll d)
{
    if(d < 0)
        N *= -1, d *= -1;
    
    if(N > 0)
        return (N - 1) / d + 1;
    else
        return N / d;
}

long long pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret *= x;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x *= x;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//拡張ユークリッド互除法
long long int ext_gcd(long long int a, long long int b, long long int &x, long long int &y)
{
  if (b == 0)
  {
    x = 1;
    y = 0;
    return a;
  }
  long long int q = a / b;
  long long int g = ext_gcd(b, a-q*b, x, y);
  long long int z = x-q*y;
  x = y;
  y = z;
  return g;
}

//aとmは互いに素, a^(-1) mod m
long long int modinv(long long int a, long long int m) 
{
  long long int x, y;
  ext_gcd(a, m, x, y);
  x %= m;
  if (x < 0)
    x += m;
  return x;
}

ll takemod(ll x,ll m){
  ll num = x;
  num %= m;
  if (num < 0)
    num += m;
  return num;
}

const ll MOD = 998244353LL;
ll N;
string S,T;

ll convert(string s){
  reverse(ALL(s));
  ll res = 0;
  rep(i,s.size()){
    if(s[i] == 'B'){
      res += (1LL << i);
    }
  }
  return res;
}

string binary(ll bina){
    string ans = "";
    for (int i = 0; bina>0 ; i++)
    {
        if(bina%2) ans.pb('1');
        else ans.pb('0');
        bina = bina/2;
    }
  reverse(ALL(ans));
  return ans;
}

string contos(ll n){
  string ns = binary(n);
  
  string ans = "";
  
  for (int i = 0; n>0 ; i++)
  {
      if(n%2) ans.pb('B');
      else ans.pb('W');
      n= n/2;
  
  }
  rep(i,N-ns.size()+2) ans.pb('W');
  reverse(ALL(ans));
  return ans;
}

int main(){
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);
  
  ll N,Q;
  cin >> N >> Q;
  ll canuse = N;
  set<pair<ll,string>> up,down; // up -> repaired
  unordered_map<string,ll> mp;
  while(Q--){
    ll t;
    cin >> t;
    // cout << t << endl;
    if(t == 1){
      ll r;
      string s;

      cin >> s >> r;
      // cout << s << " " << r << endl;

      auto info = make_pair(r,s);
      mp[s] = r;
      down.insert(info);
      // cout << info.second << " " << up.size() << " " << down.size() << endl;
      if(up.size() + down.size() > canuse){
        auto p = *down.begin();
        down.erase(p);
        cout << p.second << endl;
      }

    }else if(t == 2){
      ll x;
      cin >> x;
      canuse -= x;

      if(up.size() + down.size() > canuse){
        ll d= (up.size() +down.size())-canuse;
        rep(i,d){
          if(down.empty()){
            auto p = *up.begin();
            up.erase(p);
            cout << p.second << endl;
            continue;
          }

          auto p = *down.begin();
          down.erase(p);
          cout << p.second << endl;
        }
      }
    }else if(t == 3){
      ll x;
      string s;
      cin >> s >> x;
      // cout << s << " " << x << endl;
      auto info = make_pair(mp[s],s);
      canuse += x;
      down.erase(info);
      up.insert(info);
    }
  }
}