#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream in("priorityqueue.in");
    ofstream out("priorityqueue.out");


struct Heap{
    int siz;
    vector<int> heap;
    vector<int> ind;

   /* void siffUp(int v){
     int p;
        p = v-1 / 2;
        if( p == 0 )return ;
        if(heap[p] < heap[v])
            swap(heap[p],heap[v]);
        siffUp(p);
     }*/
      void siffUp(int v){ // работает.
       while(v>0){
        int p;
        p = (v) / 2;
        //if( p == 0 )return ;
        if(heap[p] > heap[v]){
            swap(heap[p],heap[v]);
            swap(ind[p],ind[v]);
        }
        else break;
        v=p;
        //siffUp(p);
     }}

     add(int x){
        siz++;
      ind.push_back(siz);
      heap.push_back(x);
    // cout<<"Enter"<<endl;
     siffUp(heap.size() -1); //
     }


     void siffDown(int v){ // не работает
        //cout<<"Enter1"<<endl;

        while(2*v <heap.size() ){
        int  left = 2 * v ;             // left — левый сын
        int right = 2 * v + 1;
        if(v==0){left++;right++;}            // right — правый сын
        int j = left;
        if (right < heap.size() && heap[right] < heap[left])
            j = right;
        if (heap[v] <= heap[j])
            break;
        swap(heap[v], heap[j]);
        swap(ind[v],ind[j]);
        v = j;
        //for(int i=0;i<7;i++)cout<<heap[i]<<" ";
        //cout<<endl;
            }
     }

     void decrease_key(){
            int a , b;
            in>>a>>b;
            for(int i=0;i<heap.size();i++){
                if(ind[i] == a){
                    heap[i] = b;
                    if(heap[i] >= heap[2*i] || heap[i] >= heap[2*i + 1]){ // ИЗМЕНИТЬ УСЛОВИЕ !!!!!!!!!
                        siffDown(i);
                    }

                    if (heap[i] < heap[i/2]) {
                        siffUp(i);
                    }
                }
            }

     }




     int  extractMin(){
     if(siz>0){
     int omega=heap[0];
     heap[0] = heap[heap.size()-1];
     ind [0] = ind [heap.size()-1];
     heap.pop_back();
     ind.pop_back();
     siz--;
     siffDown(0);
     return omega;
     }

     if(siz<= 0) return 1000000001;
     }




     void heapify(){
     for(int i=heap.size() ;i>=0;i--)
        siffDown(i);
     }
};



int main()
{

    bool k = 0;

    Heap please;
    please.siz=0;
    vector<int> ans;
    while (!in.eof()){
        //cout<<1;
        string d;
        in>>d;

        if(d  == "push"){
            int element;
            in>>element;
            please.add(element);

        }
       else  if(d == "extract-min"){
        ans.push_back(please.extractMin());
        }
        else if(d == "decrease-key"){
        //   int a , b;
          //  cin>>a>>b;
           // for(int i=0;i<please.heap.size();i++){
            //    if(please.ind[i] == a){
             //       please.heap[i] = b;

                please.decrease_key();
                }


         //else if(d == "lol")k=1;
           }

    //for( int i = 0; i < please.heap.size() ; i++ ){
      //  cout<<please.heap[i]<<endl;
    // }
    for(int i=0;i<ans.size();i++){
        if(ans[i] == 1000000001)
            out<<"*"<<endl;
        else
            out<<ans[i]<<endl;
    }
    //cout<<please.siz;
    //cout<<please.extractMin();
   // cout<<please.heap.size();
    //cout<<please.heap[0];
}