#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

vector<int> split(const string& s, char delim) {
    vector<int> result;
    stringstream ss(s);
    unsigned element = 0;
    string item;

    while (getline(ss, item, delim)) {
        element++;
        if (!item.empty() && element != 1) {
            result.push_back(stoi(item));
        }
    }

    return result;
}

int main() {
    vector<pair<int, int>> vec;
    ifstream fin("priorityqueue.in");
    ofstream fout("priorityqueue.out");

    string line;
    unsigned count = 0;

    while (getline(fin, line)) {
        count++;

        if (line.find("push") != string::npos) {
            int number = split(line, ' ')[0];
            vec.push_back(pair<int, int>(count, number));
            sort(vec.begin(), vec.end(), [](pair<int, int> a,
                                            pair<int, int> b) {
                return a.second < b.second;
            });
        } else if (line.find("extract-min") != string::npos) {
            if (vec.size() == 0) {
                fout << "*" << endl;
            } else {
                fout << vec[0].second << endl;
                vec.erase(vec.begin());
            }
        } else if (line.find("decrease-key") != string::npos) {
            int index = split(line, ' ')[0];
            int value = split(line, ' ')[1];

            for (int i = 0; i < vec.size(); i++) {
                if (vec[i].first == index) {
                    vec[i].second = value;
                    break;
                }
            }

            sort(vec.begin(), vec.end(), [](pair<int, int> a,
                                            pair<int, int> b) {
                return a.second < b.second;
            });
        }
    }

    fin.close();
    fout.close();

    return 0;
}