KEK

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define TASK "priorityqueue"

vector < pair < int, int > > a(2000000);
vector < int > p(2000000);
int n = 0, pi = 0, x, y;

void sift_d(int i) {
    while (2 * i + 1 < n) {
        int l = 2 * i + 1, r = 2 * i + 2;
        int j = l;
        if (r < n && a[r] < a[l]) {
            j = r;
        }
        if (a[i] <= a[j]) {
            break;
        }
        swap(a[i], a[j]);
        swap(p[a[i].second], p[a[j].second]);
        i = j;
    }
}

void sift_u(int i) {
    if (a[i] < a[(i - 1) / 2]) {
        swap(a[i], a[(i - 1) / 2]);
        swap(p[a[i].second], p[a[(i - 1) / 2].second]);
        sift_u((i - 1) / 2);
    }
}

int ex_min() {
    int min = a[0].first;
    a[0].first = INT_MAX;
    sift_d(0);
    n--;
    return min;
}

void push(int i) {
    a[n].first = i;
    a[n].second = pi;
    p[pi] = n;
    n++;
    sift_u(n - 1);
}

void decr_key(int k, int nk) {
    a[p[k - 1]].first = nk;
    sift_u(p[k - 1]);
}

int main() {

#ifdef _DEBUG
    freopen("debug.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#else
    freopen(TASK".in", "r", stdin);
    freopen(TASK".out", "w", stdout);
#endif // _DEBUG

    string s;
    while (cin >> s) {
        if (s[0] == 'p') {
            cin >> x;
            push(x);
        }
        if (s[0] == 'd') {
            cin >> x >> y;
            decr_key(x - 1, y);
        }
        if (s[0] == 'e') {
            if (n > 0) {
                cout << ex_min() << "\n";
            }
            else {
                cout << "*\n";
            }
        }
        pi++;
    }

    cout << "kek" << endl;

    return 0;
}