#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
using namespace std;

int search(vector<int> &arr, int n, int k)
{
    int r,l,mid;
    l = 0;
    r = n;
    while ((r - l) >= 1)
    {
        mid = (l + r) / 2;
        if (k < arr[mid])
        {
            r = mid;
        }else if (k > arr[mid])
        {
            l = mid;
        }else if (k == arr[mid])
        {
            return mid;
        }
    }
}

void Sink(vector<int> &arr, int k, int n)
{
    int placed = 0;
    int j = 2*k+1;
    while (placed == 0 && j <= (n-1))
    {
        if (j < (n - 1) && arr[j] < arr[j+1])
        {
            j = j + 1;
        }
        if (arr[k] >= arr[j])
        {
            placed = 1;
        }else{
            swap(arr[k], arr[j]);
        }
        k = j;
        j = 2*k + 1;
    }
}

void HeapSort(vector<int> &arr, int n)
{
    for (int i = (n-1)/2; i > -1; i--)
    {
        Sink(arr, i, n);
    }
    while (n > 0)
    {
        swap(arr[0], arr[n - 1]);
        n = n - 1;
        Sink(arr, 0, n);
    }
}

void pop(vector<int> &arr)
{
    vector<int>::iterator it;
    it = arr.begin();
    arr.erase(it);
}
void push(vector<int> &arr, int d)
{
    arr.push_back(d);
    HeapSort(arr, arr.size());
}

void decrease_key(vector<int> &arr, int key, int m)
{
    vector<int>::iterator it;
    it = arr.begin() + search(arr, arr.size(), key);
    arr.erase(it);
    push(arr, m);
}


int main()
{
    int *top = NULL;
    int *tail = NULL;
    std::vector<int> arr;

    ifstream fin("1.txt");
    ofstream fout("priorityqueue.out");

    string command;
    int num;
    vector< pair<int,int> > ar;
    int nomerstroki = 0;
    while (fin.eof() != 1)
    {
        fin >> command;
        nomerstroki++;
        if (command == "push")
        {
            fin >> num;
            push(arr, num);
            pair<int,int> pair1;
            pair1.first = nomerstroki;
            pair1.second = num;
            ar.push_back(pair1);
        } else if (command == "extract-min")
        {
            if (arr.size() > 0)
            {
                fout << arr.front() << endl;
                pop(arr);
            } else {
                fout << "*" << endl;
            }
        } else if (command == "decrease-key")
        {
            int k,k1,m;
            string s;
            fin >> k >> m;
            for(int i = 0; i < ar.size(); i++)
            {
                if (k == ar[i].first)
                {
                    k1 = ar[i].second;
                }
            }
            decrease_key(arr, k1, m);
        }
    }
    return 0;
}