#include <bits/stdc++.h>
using namespace std;
signed main(){
	int Q;
	cin >> Q;
	queue<int> q;
	multiset<int> st;
	while(Q--){
		int ty;
		cin >> ty;
		if(ty == 1){
			int num;
			cin >> num;
			q.push(num);
		}else if(ty == 2){
			if(!st.empty()){
				cout << *st.begin() << endl;
				st.erase(st.begin());
			}else{
				cout << q.front() << endl; 
				q.pop();
			}
 
		}else{
			while(!q.empty()){
				st.insert(q.front());
				q.pop();
			}
 
		}
	}
 
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnNpZ25lZCBtYWluKCl7CglpbnQgUTsKCWNpbiA+PiBROwoJcXVldWU8aW50PiBxOwoJbXVsdGlzZXQ8aW50PiBzdDsKCXdoaWxlKFEtLSl7CgkJaW50IHR5OwoJCWNpbiA+PiB0eTsKCQlpZih0eSA9PSAxKXsKCQkJaW50IG51bTsKCQkJY2luID4+IG51bTsKCQkJcS5wdXNoKG51bSk7CgkJfWVsc2UgaWYodHkgPT0gMil7CgkJCWlmKCFzdC5lbXB0eSgpKXsKCQkJCWNvdXQgPDwgKnN0LmJlZ2luKCkgPDwgZW5kbDsKCQkJCXN0LmVyYXNlKHN0LmJlZ2luKCkpOwoJCQl9ZWxzZXsKCQkJCWNvdXQgPDwgcS5mcm9udCgpIDw8IGVuZGw7IAoJCQkJcS5wb3AoKTsKCQkJfQoJCQkKCQl9ZWxzZXsKCQkJd2hpbGUoIXEuZW1wdHkoKSl7CgkJCQlzdC5pbnNlcnQocS5mcm9udCgpKTsKCQkJCXEucG9wKCk7CgkJCX0KCQkJCgkJfQoJfQoJCn0=

OQoxIDUKMSA1CjEgMwoyCjMKMgoxIDYKMwoyCg==

9
1 5
1 5
1 3
2
3
2
1 6
3
2