//#define DEBUG

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

vector<int> heap;

void sift_down(int i) {
    unsigned left = i * 2 + 1;
    unsigned right = i * 2 + 2;

    int smallest = i;

    if (left < heap.size() && heap[left] < heap[smallest])
        smallest = left;

    if (right < heap.size() && heap[right] < heap[smallest])
        smallest = right;

    if (smallest != i) {
        swap(heap[smallest], heap[i]);
        sift_down(smallest);
    }
}

void sift_up(int i) {
    if (i == 0) return;

    int parent = (i - 1) / 2;
    if (heap[i] < heap[parent]) {
        swap(heap[i], heap[parent]);
        sift_up(parent);
    }
}

void push(int val) {
    heap.push_back(val);
    sift_up(heap.size() - 1);
}

int extract_min() {
    swap(heap[0], heap[heap.size() - 1]);

    int val = heap.back();
    heap.pop_back();

    sift_down(0);

    return val;
}

bool empty() {
    return heap.empty();
}

void decrease_key(int key, int keyTo) {
    int pos;

    for (pos = 0; heap[pos] != key; ++pos);

    heap[pos] = keyTo;
    sift_up(pos);
}


// all solution is here, not in main function
void resolve(istream &in, ostream &out) {
    vector<int> ops;
    string line;

    while (getline(in, line)) {
        stringstream st(line);

        string command;
        st >> command;

        if (command == "push") {
            int val;
            st >> val;

            push(val);

            ops.push_back(val);

        } else if (command == "extract-min") {
            if (empty())
                out << '*' << endl;
            else
                out << extract_min() << endl;

            ops.push_back(-1);

        } else if (command == "decrease-key") {
            int from, to;

            st >> from >> to;

            decrease_key(ops[from - 1], to);
            ops[from - 1] = to;

            ops.push_back(-1);
        }
    }
}




// for convinient testing and debugging
string problem = "priorityqueue";
#ifndef TEST
int main() {
#ifdef DEBUG
    istream &in = cin;
    ostream &out = cout;
#else
    string instring = problem + ".in";
    string outstring = problem + ".out";
    istream &in = *(new ifstream(instring.c_str()));
    ostream &out = *(new ofstream(outstring.c_str()));
#endif

    resolve(in, out);

    out.flush();
    return 0;
}
#endif