#include <iostream>
#include <vector>
using namespace std;

long long max_s, now_s = 0;
vector<long long> a;

void Sift_Down(long long i, bool j = true){
  int l = 2 * i + 1, r = 2 * i + 2, max = i;
  if(l < now_s && a[l] > a[max]) max = l;
  if(r < now_s && a[r] > a[max]) max = r;
  if(max != i){
    long long temp = a[i];
    a[i] = a[max];
    a[max] = temp;
    Sift_Down(max);
  }
  else if(j) cout << i + 1 << " ";
}

void Sift_Up(long long i, bool j = true){
   long long pred, min = i;
  if (i % 2 == 0) pred = (i - 2) / 2;
  else pred = i / 2;
  if(pred >= 0 && a[min] > a[pred]) min = pred;
  if(min != i){
      long long t = a[i];
      a[i] = a[min];
      a[min] = t;
      Sift_Up(min);
  }
  else if(j) cout << i + 1 << endl;
}

void Extract_Max(){
  if (now_s != 0){
    long long t = a[0];
    a[0] = a[now_s - 1];
    a.pop_back();
    now_s--;
    if (now_s != 0) Sift_Down(0);
    else cout << 0 << " ";
    cout << t << endl;
  }
  else cout << -1 << endl;
}

void Delete(long long i){
  if (now_s > i) {
    long long t = a[i];
    a[i] = a[now_s - 1];
    a.pop_back();
    now_s--;
    if (now_s != 0) {
      Sift_Down(i, false);
      Sift_Up(i, false);
    }
    cout << t << endl;
  }
  else cout << -1 << endl;
}

void Insert(long long q){
  if (now_s < max_s){
    a.push_back(q);
    Sift_Up(now_s);
    now_s++;
  }
  else cout << -1 << endl;
}


int main(int argc, char const *argv[]) {
  cin >> max_s;
  int m;
  cin >> m;

  for (size_t i = 0; i < m; i++) {
    long long a1, a2;
    cin >> a1;
    if (a1 == 1) Extract_Max();
    else if(a1 == 2){
      cin >> a2;
      Insert(a2);
    }
    else{
      cin >> a2;
      Delete(a2 - 1);
    }
  }
    for (size_t i = 0; i < now_s; i++) {
      cout << a[i] << " ";
    }
  return 0;
}