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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	public static class PriorityQueue{
		int[] heap;
		int size;
		
		public PriorityQueue(){
			heap = new int[2000000];
			size = 0;
		}
		
		private void maxHeapify(int i){
			int l = i * 2 + 1;
			int r = i * 2 + 2;
		
			int largest = -1;
		
			if(l < size && heap[l] > heap[i]){
				largest = l;
			}else{
				largest = i;
			}
		
			if(r < size && heap[r] > heap[largest]){
				largest = r;
			}
		
			if(largest != i){
				int tmp = heap[i];
				heap[i] = heap[largest];
				heap[largest] = tmp;
			
				maxHeapify(largest);
			}
		}
		
		public void insert(int value){
			heap[size++] = value;
			
			int current = size - 1;
			while(current != 0 && heap[(current - 1) / 2] < heap[current]){
				int tmp = heap[(current - 1) / 2];
				heap[(current - 1) / 2] = heap[current];
				heap[current] = tmp;
				
				current = (current - 1) / 2;
			}
		}
		
		public int extractMax(){
			final int ret = heap[0];
			heap[0] = heap[--size]; 
			this.maxHeapify(0);
			
			return ret;
		}
		
		public String toString(){
			StringBuilder sb = new StringBuilder();
			sb.append("[");
			for(int i = 0; i < size; i++){
				if(i != 0){
					sb.append(", ");
				}
				sb.append(heap[i]);
			}
			sb.append("]");
		
			return sb.toString();
		}
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		PriorityQueue queue = new PriorityQueue();
		while(true){
			final String ops = sc.next();
			
			//System.out.println(queue);
			
			if("insert".equals(ops)){
				final int value = sc.nextInt();
				queue.insert(value);
			}else if("extract".equals(ops)){
				System.out.println(queue.extractMax());
			}else if("end".equals(ops)){
				break;
			}
			
		}
		
	}

	public static class Scanner {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public void close() throws IOException {
			br.close();
		}
	}

}