#include <iostream>

using namespace std;

struct element {
    element *prev;
    int value;
    element *start2; //wskaznik na poczatek podlisty w liscie (tam wartosci)
    element *end2; //wskaznik na koniec podlisty w liscie (tam wartosci)
    element *next;
};

void newList(element **start, element **end, int ans1, int ans2) {
    *start = new element;
    *end = *start;
    (*start)->next = NULL;
    (*start)->prev = NULL;
    (*start)->value = ans1;

    (*start)->start2 = new element;
    (*start)->end2 = (*start)->start2;
    (*start)->start2->next = NULL;
    (*start)->start2->prev = NULL;
    (*start)->start2->value = ans2;
}

int numElements(element *start) {
    int counter = 0;
    while (start != NULL) {
        counter++;
        start = start->next;
    }
    return counter;
}

void sortList(element *start) {
    int numElem = numElements(start);
    element *ptr1 = start;
    element *ptr2;
    int container;

    if (numElem > 1) {
        for (int i = 0; i < numElem; i++) {
            ptr2 = ptr1;
            for (int j = 0; j < numElem - 1; j++) {
                if (ptr2->value < ptr2->next->value) {
                    container = ptr2->value;
                    ptr2->value = ptr2->next->value;
                    ptr2->next->value = container;
                }
                ptr2 = ptr2->next;
            }
        }
    }
}

void printList(element *start) {
    if (start != NULL) {
        sortList(start);
        while (start != NULL) {
            printf("%d ", start->value);
            start = start->next;
        }
    }
    else
        printf("na");

    printf("\n");
}

void addFirst(element *&start, int val) {
    element *newElem = new element;
    newElem->value = val;
    newElem->next = start;
    newElem->prev = NULL;
    start->prev = newElem;
    start = newElem;
}

element* addLast(element *&end, int val) {
    element *newElem = new element;
    newElem->value = val;
    newElem->next = NULL;
    newElem->prev = end;
    end->next = newElem;
    end = newElem;
    return newElem;
}

element* returnElement(element *start, int x) {
    if (x < 1)
        return NULL;
    for (int i = 1; i < x && start != NULL; i++)
        start = start->next;
    return start;
}

bool change(element *start, int ind, int val) {
    element *ptr = returnElement(start, ind);
    if (ptr != NULL) {
        ptr->value = val;
        return true;
    }
    else return false;
}

void putBefore(element *ptr, int val) {
    element *newElem = new element;
    newElem->value = val;
    newElem->next = ptr;
    newElem->prev = ptr->prev;
    ptr->prev->next = newElem;
    ptr->prev = newElem;
}

void putAfter(element *ptr, int val) {
    element *newElem = new element;
    newElem->value = val;
    newElem->next = ptr->next;
    newElem->prev = ptr;
    ptr->next->prev = newElem;
    ptr->next = newElem;
}

//Funkcja dodaje element, zachowujac kolejnosc malejaca wartosci 'value'
element* insert(element **start, element **end, int val) {
    element *ptr = *start;

    while (ptr->value > val && ptr->next != NULL)
        ptr = ptr->next;

    if (ptr->value > val) {
        if (ptr->next == NULL) {
            addLast(*end, val);
            return *end;
        }
        else {
            putAfter(ptr, val);
            return ptr->next;
        }
    }
    else {
        if (ptr->prev == NULL) {
            addFirst(*start, val);
            return *start;
        }
        else {
            putBefore(ptr, val);
            return ptr->prev;
        }
    }
    return NULL;
}

element* search(element *start, int szukany) {
    while (start != NULL && start->value != szukany)
        start = start->next;

    if (start == NULL)
        return NULL;
    else
        return start;
}

bool deleteFirst(element *&start) {
    if (start != NULL && start->next != NULL) {
        element *temp;
        temp = start->next;
        delete start;
        start = temp;
        start->prev = NULL;
        return true;
    }
    return false;
}

bool deleteLast(element *&end) {
    if (end != NULL && end->prev != NULL) {
        element *temp;
        temp = end->prev;
        delete end;
        end = temp;
        end->next = NULL;
        return true;
    }
    return false;
}

bool deleteElement(element *ptr) {
    if (ptr != NULL && ptr->next != NULL && ptr->prev != NULL) {
        ptr->prev->next = ptr->next;
        ptr->next->prev = ptr->prev;
        delete ptr;
        return true;
    }
    return false;
}

void freeList(element *&start, element *&end) {
    element *temp;
    while (start != NULL) {
        temp = start;
        start = start->next;
        delete temp;
    }
    end = NULL;
}

void aFun(element **start, element **end, int ans1, int ans2) {
    //Jesli lista nie istnieje, to tworzymy ja i wypelniamy od razu potrzebnymi danymi (problem z glowy)
    if (*start == NULL)
        newList(start, end, ans1, ans2);

    else {
        element *ptr = search(*start, ans1);
        //Sprawdzamy czy group o numerze ans1 istnieje:
        //1) Jesli tak, to ptr = wskaznik na ta grupke na liscie
        //2) Jesli nie, to ptr = NULL

        //Jesli nie znalazlo nam grupy o numerze ans1: funkcja wrzuca ans1 na liste, zachowujac kolejnosc malejaca (tworzymy grupe)
        if (ptr == NULL) {
            ptr = addLast(*end, ans1);
            //przy okazji zwraca wskaznik na wlasnie dodany element i wykorzystujemy go do utworzenia podlisty
            ptr->start2 = new element;
            ptr->start2->next = NULL;
            ptr->start2->prev = NULL;
            ptr->end2 = ptr->start2;
            ptr->start2->value = ans2;
        }
        else {
            addLast(ptr->end2, ans2);
        }
    }
}

void pFun(element *start, int ans1) {
    element *ptr = search(start, ans1);
    if (ptr != NULL) {
        printList(ptr->start2);
    }
    else
        printf("na\n");
}

void iFun(element **start, element **end, int ans1, int ans2, int ans3) {
    element *ptr = search(*start, ans1);

    //jesli jest taka grupa
    if (ptr != NULL) {
        //nowy wskaznik, dzialajacy w podliscie
        element *ptr2 = search(ptr->start2, ans2);
        if (ptr2 != NULL) ptr2->value = ans3;
        else
            printf("na\n");
    }
    else
        printf("na\n");
}

element *MaxValue(element *start) {
    element *max = start;
    while (start != NULL) {
        if (start->value > max->value)
            max = start;
        start = start->next;
    }
    return max;
}

void eFun(element **start, element **end, int ans1) {
    element *ptr = search(*start, ans1);
    if (ptr != NULL) {
        element *ptrValue = MaxValue(ptr->start2);
        printf("%d\n", ptrValue->value);

        //Czy wartosc, ktora mamy usunac byla jedyna na liscie? Jesli tak, usun takze grupe
        if (ptrValue->prev == NULL) {
            if (ptrValue->next == NULL) {
                freeList(ptr->start2, ptr->end2);

                //Usuwanie elementu glownej listy
                if (ptr->prev == NULL) {
                    if (ptr->next == NULL) freeList(*start, *end);
                    else deleteFirst(*start);
                }
                else if (ptr->next == NULL)
                    deleteLast(*end);
                else
                    deleteElement(ptr);
            }
            else deleteFirst(ptr->start2);
        }
        else if (ptrValue->next == NULL)
            deleteLast(ptr->end2);
        else
            deleteElement(ptrValue);

    }
    else
        printf("na\n");
}

void mFun(element **start, element **end, int ans1, int ans2) {
    element *group1 = search(*start, ans1);
    element *group2 = search(*start, ans2);

    if (group2 != NULL) {

        if (group1 == NULL) {
            //Jesli grupa 1 nie istnieje, to zmieniemay nazwe na grupy2
            group2->value = ans1;
        }
        else {
            group1->end2->next = group2->start2;
            group2->start2->prev = group1->end2;
            group1->end2 = group2->end2;

            //Jesli nie udalo sie usunac elementu, to znaczy, ze element byl ostatni lub pierwszy
            if (!deleteElement(group2)) {
                if (group2->prev == NULL) deleteFirst(*start);
                else deleteLast(*end);
            }
        }
    }
}


int main() {
    element *start = NULL;
    element *end = NULL;

    int nrOfOperations;
    char operation;
    int ans1, ans2, ans3;

    scanf("%d", &nrOfOperations);

    for (int i = 0; i < nrOfOperations; i++) {

        scanf(" %c", &operation);

        switch (operation) {
        case 'a':
            scanf("%d %d", &ans1, &ans2);
            aFun(&start, &end, ans1, ans2);
            break;
        case 'e':
            scanf("%d", &ans1);
            eFun(&start, &end, ans1);
            break;
        case 'p':
            scanf("%d", &ans1);
            pFun(start, ans1);
            break;
        case 'm':
            scanf("%d %d", &ans1, &ans2);
            mFun(&start, &end, ans1, ans2);
            break;
        case 'i':
            scanf("%d %d %d", &ans1, &ans2, &ans3);
            iFun(&start, &end, ans1, ans2, ans3);
            break;
        default:
            printf("na\n");
            break;
        }
    }

    //system("pause");
    return 0;
}