#als#kopiec

#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>

using namespace std;

struct kopiec {
    int wartosc;
    kopiec *left, *right, *up;
};

struct kolejka {
    bool direction;
    kolejka *next, *prev;
};

int index = 0;

///////////////////////////

void naKopiec(kopiec *root, int wartosc);

void showTree(kopiec *root);

void usuwanie(kopiec *root);

//////////////////////////

int main() {

    kopiec *root = new kopiec;
    int wartosc;
    int opcja=-2;

    while(opcja!=-1){
        cin >> opcja;
        switch(opcja){
            case -1:
                break;
            case 0:
                cin >> wartosc;
                naKopiec(root, wartosc);
                break;
            case 1:
                usuwanie(root);
                break;
            case 2:
                showTree(root);
                break;
        }
    }

    return 0;
}

/// DODAWANIE

void balans(kopiec *nowy) {
    if (nowy->up == NULL)return;
    else if (nowy->wartosc < nowy->up->wartosc) return;
    else if (nowy->wartosc > nowy->up->wartosc) {
        int value = nowy->up->wartosc;
        nowy->up->wartosc = nowy->wartosc;
        nowy->wartosc = value;
        balans(nowy->up);
    }

}

void naKopiec(kopiec *root, int wartosc) {
    if (root->wartosc == NULL) {
        root->wartosc = wartosc;
        root->right = NULL;
        root->left = NULL;
        root->up = NULL;
        index++;
    } else {
        index++;
        kolejka *stos = new kolejka;
        kolejka *tmp1 = new kolejka;
        tmp1 = stos;
        int indexCopy = index;
        while (indexCopy != 1) {
            kolejka *kierunek = new kolejka;
            tmp1->next = kierunek;
            kierunek->prev = tmp1;
            if (indexCopy % 2 == 0) kierunek->direction = 0;
            else kierunek->direction = 1;
            indexCopy = indexCopy / 2;
            tmp1 = tmp1->next;
        }
        kopiec *nowy = new kopiec;
        kopiec *tmp2 = root;
        nowy->wartosc = wartosc;
        nowy->left = NULL;
        nowy->right = NULL;
        while (tmp1 != stos) {
            if (tmp1->direction == 0) {
                if (tmp2->left == NULL) {
                    tmp2->left = nowy;
                    nowy->up = tmp2;
                } else {
                    tmp2 = tmp2->left;
                    tmp1 = tmp1->prev;
                }
            } else if (tmp1->direction == 1) {
                if (tmp2->right == NULL) {
                    tmp2->right = nowy;
                    nowy->up = tmp2;
                } else {
                    tmp2 = tmp2->right;
                    tmp1 = tmp1->prev;
                }
            }
        }

        balans(nowy);
    }

}

/// WYSWIETLANIE

void showTree(kopiec *root) {
    kopiec *tmp = root;

    cout << root->wartosc << " ";

    if (tmp->left != NULL) showTree(tmp->left);

    if (tmp->right != NULL) showTree(tmp->right);
}

/// USUWANIE

void balans2(kopiec *root) {
    if (root->wartosc > root->left->wartosc && root->wartosc > root->right->wartosc) return;
    else if (root->wartosc > root->left->wartosc && root->wartosc < root->right->wartosc){
        int value = root->wartosc;
        root->wartosc = root->right->wartosc;
        root->right->wartosc = value;
        balans2(root->right);
    } else{
        int value = root->wartosc;
        root->wartosc = root->left->wartosc;
        root->left->wartosc = value;
        balans2(root->left);
    }
}

void usuwanie(kopiec *root) {

    kolejka *stos = new kolejka;
    kolejka *tmp1 = new kolejka;
    tmp1 = stos;
    int indexCopy = index;
    while (indexCopy != 1) {
        kolejka *kierunek = new kolejka;
        tmp1->next = kierunek;
        kierunek->prev = tmp1;
        if (indexCopy % 2 == 0) kierunek->direction = 0;
        else kierunek->direction = 1;
        indexCopy = indexCopy / 2;
        tmp1 = tmp1->next;
    }
    ///
    kopiec *tmp2 = root;

    while (tmp1 != stos) {
        if (tmp1->direction == 0) {
            tmp2 = tmp2->left;
            tmp1 = tmp1->prev;
        } else if (tmp1->direction == 1) {
            tmp2 = tmp2->right;
            tmp1 = tmp1->prev;
        }
    }
    int value = root->wartosc;
    root->wartosc = tmp2->wartosc;
    tmp2->wartosc = value;
    tmp2 = tmp2->up;
    if (tmp2->right->wartosc == value) {
        delete (tmp2->right);
        tmp2->right = NULL;
    } else {
        delete (tmp2->left);
        tmp2->left = NULL;
    }

    balans2(root);



////
}