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.Arrays;
import java.util.Scanner;
 
public class Main {
    public int[] link;
    private int curr;
    public int size=3000000;
     
    public Main() {
        this.link= new int[size];
        this.curr=0;
    }
     
    public void insert(int k) {
        this.link[curr]=k;
        this.curr++;
        int m =curr;
        //System.out.println(m);
        while ((m>=2)&&(this.link[m-1]>=this.link[m/2-1])) {
            //System.out.println(m);
            this.link[m-1]=this.link[m/2-1];
            this.link[m/2-1]=k;
            m=m/2;
        }
    }
     
    public void maxHeap(int[] a,int i) {
        int l = this.link[2*i-1];
        int r = this.link[2*i];
        int par = this.link[i-1];
        int largest=i;
        if ((2*i<=curr)&&(l>par)) {
            largest = 2*i;
        }
         
        if ((2*i+1<=curr)&&(r>this.link[largest-1])){
            largest = 2*i+1;
        }
        if (largest != i) {
            int m = this.link[i-1];
            this.link[i-1]=this.link[largest-1];
            this.link[largest-1]=m;
            this.maxHeap(this.link,largest);
        }   
    }
     
    //public void buildMaxHeap(int[] m) {
    //  for (int i=(curr+1)/2;i>0;i--) {
    //      this.maxHeap(m,i);
    //  }
    //}
 
     
    public int extract() {
        //this.buildMaxHeap(this.link);
        //System.out.println(Arrays.toString(this.link));
        int t = this.link[0];
        if (curr>0) {
            this.link[0]=this.link[--curr];
        }
        this.link[curr]=0;
        //System.out.println(Arrays.toString(this.link));
        this.maxHeap(this.link, 1);
        //System.out.println(Arrays.toString(this.link));
        return t;
         
    }
     
    public static void main(String[] wjy) {
        Scanner sc = new Scanner(System.in);
        Main lk = new Main();
        boolean suit =true;
        while (suit) { 
            String a = sc.next();
            if (a.equals("end")) {
                suit = false;
            }
            else if(a.equals("extract")) {
                System.out.println(lk.extract());
            }
            else {
                int j=(int) sc.nextInt();
                lk.insert(j);
            }
        }
        sc.close();
    }
}
