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 int negativeInf = Integer.MIN_VALUE;
    public static void main (String args[]){
        //初期処理
        // Scanner sc=new Scanner(System.in);
        // int n=Integer.parseInt(sc.nextLine());
        // String[] sElementArray=sc.nextLine().split(" ");
        // //int[] array=Arrays.stream(sElementArray).mapToInt(Integer::parseInt).toArray();
        // int[] array=new int[n+1];
        // for(int i=0;i<n;i++){
        //     array[i+1]=Integer.parseInt(sElementArray[i]);
        // }
        // array[0]=negativeInf;
        // sc.close();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           try{
                //int n= Integer.parseInt(br.readLine());
                //int[] array = Arrays.stream(sElementArray).mapToInt(Integer::parseInt).toArray();
                ArrayList<Integer> heapArray=new ArrayList<Integer>();
                heapArray.add(negativeInf);//0番目は使わないので埋める

                while( true ){
                    String[] sArray=br.readLine().split(" ");
                    if(sArray[0].equals("insert")){
                        int number = Integer.parseInt(sArray[1]);
                        insert(heapArray,number);
                    }
                    if(sArray[0].equals("extract")){
                        int ans = extract(heapArray);
                        System.out.println(ans);
                    }
                    if(sArray[0].equals("end")){
                        break;
                    }
                    
                }
                
            }catch(IOException e){e.printStackTrace();}



        

    }

    static void buildMaxHeap(ArrayList<Integer> array){
        for(int i=(array.size()-1)/2;i>=1;i--){
            maxHeapify(i, array);
        }
    }
    
    //return index of each node
    static int parent(int h){return h/2;}
    static int left(int h){return 2*h;}
    static int right(int h){return 2*h+1;}

    static void maxHeapify(int k,ArrayList<Integer> array){
        int indexOfLargestKey=k;
        int l=0;
        int r=0;
        if(2*k<array.size()) {
            l=left(k);
        }
        if(2*k+1<array.size()){
            r=right(k);
        }
        
        if(array.get(indexOfLargestKey)<array.get(l)){
            indexOfLargestKey=l;
        }
        if(array.get(indexOfLargestKey)<array.get(r)){
            indexOfLargestKey=r;
        }

        if(array.get(indexOfLargestKey) != array.get(k)){
            swap(array,indexOfLargestKey,k);
            maxHeapify(indexOfLargestKey, array);
        }
    }

    static void swap(ArrayList<Integer> array,int n,int m){
        int tmp=array.get(n);
        array.set(n, array.get(m));
        array.set(m, tmp);
    }

    static void insert(ArrayList<Integer> heapArray,int number){
        heapArray.add(number);
        //buildMaxHeap(heapArray);
        int k=heapArray.size()-1;
        while(parent(k)>=1 && heapArray.get(k)>heapArray.get(parent(k))){
            swap(heapArray,k,parent(k));
            k=parent(k);
        }
    }

    static int extract(ArrayList<Integer> heapArray){
        int popedNumber =heapArray.get(1);
        int h = heapArray.size()-1;
        heapArray.set(1,heapArray.get(h));
        heapArray.remove(h);
        maxHeapify(1, heapArray);
        return popedNumber;
    }
}
    
