#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    map<long long, long long> mp;
    long long m, n, k, p;
    while(cin>>m){
        if(m == 0){
            break;
        }
        else if(m == 1){
            cin>>k>>p;
            mp.insert({p, k});

        }
        else if(m == 2){
            if(mp.empty()){
                cout<<0<<endl;
            }
            else{
                auto it = prev(mp.end());
                cout<<it->second<<endl;
                mp.erase(it);
            }
        }
        else if(m == 3){
            if(mp.empty()){
                cout<<0<<endl;
            }
            else{
                cout<<mp.begin()->second<<endl;
                mp.erase(mp.begin());
            }
        }
    }
    return 0;
}

C++ solution using map