#include<bits/stdc++.h> using namespace std; int pro; int k; int p; struct point { int k; int p; }; vector<point> path; vector<point> tmp; vector<int> a; bool b=0; int main() { while(cin>>pro) { if(pro==0) { break; } if(pro==2) { if(path.size()==0) { a.push_back(0); } else { a.push_back(path[0].k); reverse(path.begin(),path.end()); path.pop_back(); reverse(path.begin(),path.end()); } } else if(pro==3) { if(path.size()==0) { a.push_back(0); } else { a.push_back(path[path.size()-1].k); path.pop_back(); } } else if(pro==1) { cin>>k; cin>>p; if(path.size()==0) { path.push_back({k,p}); } else { b=0; for(int i=path.size()-1;i>=0;i--) { if(path[i].p<p) { tmp.push_back({path[i].k,path[i].p}); path.pop_back(); } else { b=1; path.push_back({k,p}); break; } } if(b==0) { path.push_back({k,p}); } for(int i=tmp.size()-1;i>=0;i--) { path.push_back({tmp[i].k,tmp[i].p}); tmp.pop_back(); } } } } for(int i=0;i<a.size();i++) { cout<<a[i]; cout<<endl; } return 0; }