A priority queue is a data structure which maintains a set $S$ of elements, each of with an associated value (key), and supports the following operations:

* $insert(S, k)$: insert an element $k$ into the set $S$
* $extractMax(S)$: remove and return the element of $S$ with the largest key



Write a program which performs the $insert(S, k)$ and $extractMax(S)$ operations to a priority queue $S$. The priority queue manages a set of integers, which are also keys for the priority.

Constraints

* The number of operations $\leq 2,000,000$
* $0 \leq k \leq 2,000,000,000$

Input

Multiple operations to the priority queue $S$ are given. Each operation is given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an integer element to be inserted to the priority queue.

The input ends with "end" operation.

Output

For each "extract" operation, print the element extracted from the priority queue $S$ in a line.

Example

Input

insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end


Output

8
10
11
2
import java.util.*;
import java.io.*;

public class Main {
	static class PriorityQueue {
		long[] heap = new long[2000000];
		int size = 0;
	}
	public static void main(String[]  args) {
		PriorityQueue s = new PriorityQueue();
		
		out:while (true) {
			next();
			switch (nextbuf[0]) {
				case 'i':
					insert(s, nextLong());
					break;
				case 'e':
					switch (nextbuf[1]) {
						case 'x':
							System.out.println(extractMax(s));
							break;
						case 'n':
							break out;
					}
					break;
			}
		}
	}

	static int parent(int i) {
		return (i  - 1) / 2;
	}

	static int left(int i) {
		return i * 2 + 1;
	}

	static int right(int i) {
		return left(i) + 1;
	}
	
	static void maxheapify(PriorityQueue s, int i) {
		int l = left(i);
		int r = right(i);
		int max = i;
		
		if (l < s.size && s.heap[l] > s.heap[max]) {
			max = l;
		}
		if (r < s.size && s.heap[r] > s.heap[max]) {
			max = r;
		}
		
		if (max != i) {
			long temp = s.heap[i];
			s.heap[i] = s.heap[max];
			s.heap[max] = temp;
			
			maxheapify(s, max);
		}
	}
	
	static void insert(PriorityQueue s, long k) {
		s.heap[s.size] = k;
		int i = s.size ++;
		
		while(i > 0 && s.heap[parent(i)] < s.heap[i]) {
			long tmp = s.heap[parent(i)];
			s.heap[parent(i)] = s.heap[i];
			s.heap[i] = tmp;
			
			i = parent(i);
		}
	}
	
	static long extractMax(PriorityQueue s) {
		long max = s.heap[0];
		
		s.heap[0] = s.heap[-- s.size];
		maxheapify(s, 0);
		
		return max;
	}
	
	private static byte[] buf = new byte[1 << 20];
	private static int len = 0;
	private static int ptr = 0;

	private static byte read() {
		if (ptr >= len) {
			try {
				len = System.in.read(buf);
			} catch (Exception e) {
			}
			ptr = 0;
		}

		return buf[ptr++];
	}

	private static long nextLong() {
		long num = 0;

		byte b = read();
		while(!Character.isDigit(b) && b != '-') b = read();
		int sign;
		if (b == '-') {
			sign = -1;
			b = read();
			if (!Character.isDigit(b)) return 0;
		} else {
			sign = 1;
		}

		while(Character.isDigit(b)) {
			num *= 10;
			num += sign * (b - '0');
			b = read();
		}

		return num;
	}

	private static byte[] nextbuf = new byte[11];
	private static int nextlen;

	private static void next() {
		nextlen = 0;

		byte b = read();
		while(!Character.isAlphabetic(b) && !Character.isDigit(b)) b = read();
		while(Character.isAlphabetic(b) || Character.isDigit(b)) {
			nextbuf[nextlen++] = b;
			b = read();
		}
	}
} 

