#define _CRT_SECURE_NO_WARNINGS
#include<utility>
using std::swap;
struct PairingHeap {
	struct Node {
		int key;
		Node *head, *next;
		Node(int key) : key(key), head(0), next(0) { }
	} *r;

	Node *merge(Node *i, Node *j) {
		if (!i || !j) return i ? i : j;
		if (i->key < j->key) swap(i, j);
		j->next = i->head; i->head = j;
		return i;
	}
	Node *mergeList(Node *s) {
		Node n(0);
		while (s) {
			Node *a = s, *b = 0;
			s = s->next; a->next = 0;
			if (s) { b = s; s = s->next; b->next = 0; }
			a = merge(a, b); a->next = n.next;
			n.next = a;
		} // s == 0
		while (n.next) {
			Node *j = n.next;
			n.next = n.next->next;
			s = merge(j, s);
		}
		return s;
	}
	int  top() { return r->key; }
	void pop() { r = mergeList(r->head); }
	void push(int key) { r = merge(r, new Node(key)); }
	bool empty() { return !r; }
	PairingHeap() : r(0) { }
};
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <utility>

template <class T> class pairing_heap {

public:
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;

private:
	struct node_t {
		value_type value;
		std::unique_ptr<node_t> left, right;
		template <class... Args>
		node_t(Args &&... args)
			: value(std::forward<Args>(args)...), left(), right() {}
	};
	using pointer = std::unique_ptr<node_t>;
	pointer root;
	size_type s;
	static pointer merge(pointer &&x, pointer &&y) {
		if (!x)
			return std::move(y);
		if (x->value< y->value)
			std::swap(x, y);
		y->right = std::move(x->left);
		x->left = std::move(y);
		return std::move(x);
	}
	static pointer mergelist(pointer curr) {
		pointer head, temp;
		while (curr) {
			temp = std::move(curr->right);
			if (!temp) {
				curr->right = std::move(head);
				head = std::move(curr);
				break;
			}
			if (curr->value> temp->value) {
				curr->right = std::move(head);
				head = std::move(curr);
				curr = std::move(temp->right);
				temp->right = std::move(head->left);
				head->left = std::move(temp);
			}
			else {
				curr->right = std::move(temp->left);
				temp->left = std::move(curr);
				curr = std::move(temp->right);
				temp->right = std::move(head);
				head = std::move(temp);
			}
		}
		if (head) {
			while (temp = std::move(head->right), temp) {
				if (head->value> temp->value) {
					head->right = std::move(temp->right);
					temp->right = std::move(head->left);
					head->left = std::move(temp);
				}
				else {
					head->right = std::move(temp->left);
					temp->left = std::move(head);
					head = std::move(temp);
				}
			}
		}
		return std::move(head);
	}

public:
	pairing_heap() : root(), s(0) {}

	bool empty() const { return !root; }
	size_type size() const { return s; }

	const_reference top() const {
		assert(root);
		return root->value;
	}

	void push(const value_type &x) {
		root = merge(std::move(root), std::make_unique<node_t>(x));
		++s;
	}
	void push(value_type &&x) {
		root = merge(std::move(root), std::make_unique<node_t>(std::move(x)));
		++s;
	}
	template <class... Args> void emplace(Args &&... args) {
		root = merge(std::move(root),
			std::make_unique<node_t>(std::forward<Args>(args)...));
		++s;
	}

	void pop() {
		assert(root);
		root = mergelist(std::move(root->left));
		--s;
	}

	pairing_heap &meld(pairing_heap &other) {
		if (!other.empty()) {
			s += other.s;
			other.s = 0;
			root = merge(std::move(root), std::move(other.root));
		}
		return *this;
	}
	pairing_heap &operator+=(pairing_heap &other) { return meld(other); }
};
#include<cstdio>
#include<string>
void scan(std::string &s) {
	s.clear();
	int c = fgetc(stdin);
	while (c == ' ' || c == '\n') c = fgetc(stdin);
	while (c != ' '&&c != '\n') {
		s.push_back(c);
		c = fgetc(stdin);
	}
}

int main() {
	pairing_heap<int> Q;
	std::string s;
	int k;
	while (scan(s),s[2] != 'd') {
		if (s[0] == 'i') {
			scanf("%d", &k);
			Q.push(k);
		}
		else {
			printf("%d\n", Q.top());
			Q.pop();
		}
	}
	return 0;
}


Measured memory_bytes: 34032