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.Collections;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Priorityqueue {
		public void priorityqueue (InputReader ir) {
			
			Queue<Integer> pq = new PriorityQueue<> (Collections.reverseOrder());;
			StringBuilder sb = new StringBuilder ();
			
			while (true) {
				
				String ord = ir.nextString();
				
				if (ord.equals("end")) break;
				
				if (ord.equals("insert")) pq.add(ir.nextInt());
				else if (ord.equals("extract")) sb.append(pq.poll()).append("\n"); 
				
			}
			
			System.out.print(sb);
			
		}
	}

	static class InputReader {
		BufferedReader br;
		StringTokenizer st;
		
		public String nextString() {
			
			 while (!st.hasMoreTokens()) {
	                try {
	                    st = new StringTokenizer(br.readLine(), " ");
	                } catch (IOException e) {
	                    throw new InputMismatchException();
	                }
	            }
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(nextString());
		}
					
		public InputReader (InputStream inputStream) {
			br = new BufferedReader (new InputStreamReader (inputStream));
			st = new StringTokenizer ("");
		}
		
	}
	
	public static void main (String[] args) {
		InputStream inputStream = System.in;
		InputReader in = new InputReader (inputStream);
		Priorityqueue obj = new Priorityqueue ();
		obj.priorityqueue (in);
	}
	
	
}

