/*
 * File:   main.cpp
 * Author: Morteza
 *
 * Created on November 4, 2010, 5:54 PM
 */

#include <stdio.h>
#include <math.h>
int NewIndex;

class Node {
public:
    //Node* Parent;

    char Label;
    int Depth;
    Node* Parents[20];

    Node(Node* Parent, char Label) {
        this->Label = Label;
        if (Parent == NULL) {
            Depth = 1;
            for (int i = 0; i < 20; i++)
                Parents[i] = NULL;
            return;
        }
        Parents[0] = Parent;
        Depth = Parent->Depth + 1;
        int i;
        for (i = 1;; i++) {
            Parents[i] = Parents[i - 1]->Parents[i - 1];
            if (Parents[i] == NULL)
                break;
        }
        for (; i < 20; i++)
            Parents[i] = NULL;


    }

    Node* Find_iParent(int Index) {

        Node* iParent = this;

        int tmp = pow(2, 20);
        int stp = 20;

        while (Index) {

            while (Index < tmp) {
                tmp /= 2;
                --stp;
            }
            iParent = iParent->Parents[stp];
            Index = Index % tmp;
        }

        return iParent;
    }

    Node* Remove_iParent(Node* other, int size) {
        if (size <= Depth)
            if (Find_iParent(size - 1) == other)
                return Find_iParent(size - 2);
        if (other->Parents[0])
            return other->Parents[0];
        return Find_iParent(Depth - 1);
    }



};

class Strings {
public:
    Node* Left;
    Node* Right;
    int Size;

    Strings() {
        Left = NULL;
        Right = NULL;
        Size = 0;
    }

};


Strings Data[1000001];

void AddRight(int Index, char Label) {

    if (Data[Index].Size == 0) {
        Data[NewIndex].Right = Data[NewIndex].Left = new Node(NULL, Label);
        Data[NewIndex].Size = 1;
        return;
    }

    Data[NewIndex].Right = new Node(Data[Index].Right, Label);
    Data[NewIndex].Left = Data[Index].Left;
    Data[NewIndex].Size = Data[Index].Size + 1;

}

void AddLeft(int Index, char Label) {

    if (Data[Index].Size == 0) {
        Data[NewIndex].Left = Data[NewIndex].Right = new Node(NULL, Label);
        Data[NewIndex].Size = 1;
        return;
    }

    Data[NewIndex].Left = new Node(Data[Index].Left, Label);
    Data[NewIndex].Right = Data[Index].Right;
    Data[NewIndex].Size = Data[Index].Size + 1;
}

void RemoveRight(int Index) {

    if (Data[Index].Size == 1) {
        Data[NewIndex].Right = NULL;
        Data[NewIndex].Left = NULL;
        Data[NewIndex].Size = 0;
        return;
    }

//    Data[NewIndex].Right = Data[Index].Left->Remove_iParent(Data[Index].Right, Data[Index].Size);
//    Node * Remove_iParent(Node* other, int size) {
//        if (size <= Depth)
//            if (Find_iParent(size - 1) == other)
//                return Find_iParent(size - 2);
//        if (other->Parents[0])
//            return other->Parents[0];
//        return Find_iParent(Depth - 1);
//    }

    if (Data[Index].Size <= Data[Index].Left->Depth)

        if (Data[Index].Left->Find_iParent(Data[Index].Size - 1) == Data[Index].Right)

            Data[NewIndex].Right = Data[Index].Left->Find_iParent(Data[Index].Size - 2);

    if (Data[Index].Right->Parents[0])

        Data[NewIndex].Right = Data[Index].Right->Parents[0];

    Data[NewIndex].Right = Data[Index].Left->Find_iParent(Data[Index].Left->Depth - 1);




    Data[NewIndex].Left = Data[Index].Left;
    Data[NewIndex].Size = Data[Index].Size - 1;
}

void RemoveLeft(int Index) {

    if (Data[Index].Size == 1) {
        Data[NewIndex].Left = NULL;
        Data[NewIndex].Right = NULL;
        Data[NewIndex].Size = 0;
        return;
    }

    Data[NewIndex].Left = Data[Index].Right->Remove_iParent(Data[Index].Left, Data[Index].Size);
    Data[NewIndex].Right = Data[Index].Right;
    Data[NewIndex].Size = Data[Index].Size - 1;
}

int main() {

    int Index;
    char Label;

    int n;
    scanf("%d", &n);

    char *command = new char[20];

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

        ++NewIndex;

        scanf("%s", command);

        if (command[6] == 'T') {
            scanf("%d %c", &Index, &Label);
            AddLeft(Index, Label);
        } else if (command[6] == 'H') {
            scanf("%d %c", &Index, &Label);
            AddRight(Index, Label);
        } else if (command[6] == 'L') {
            scanf("%d", &Index);
            RemoveLeft(Index);
        } else if (command[6] == 'R') {
            scanf("%d", &Index);
            RemoveRight(Index);
        }
        if (Data[NewIndex].Size != 0)
            printf("%c %c\n", Data[NewIndex].Left->Label, Data[NewIndex].Right->Label);
        else
            printf("empty\n");
    }
    return 0;
}