#include <bits/stdc++.h>

using namespace std;

ofstream fout ("secv8.out");
class Treap
{
public:
    struct treapuri
    {
        treapuri *st;
        treapuri *dr;
        int valoare;
        int greutate;
        int subarbore;
        int inversiune;
        treapuri (treapuri *leftson, treapuri *rightson, int valoare1, int subarbore1, int greutate1, int inversiune1)
        {
            this->st = leftson;
            this->dr = rightson;
            this->valoare = valoare1;
            this->subarbore = subarbore1;
            this->greutate = greutate1;
            this->inversiune = inversiune1;
        }
    };
    treapuri *root, *NILL, *st, *dr;
    Treap()
    {
        srand(time(NULL));
        NILL = new treapuri(NULL, NULL, 0, 0, 0, 0);
        root = NILL;
    }
    int Random_Generator_Number()
    {
        return (1LL*rand()*rand()*rand())%6666029;
    }
    void Update (treapuri *& node)
    {
        if (node == NILL)
            return;
        if (node->inversiune==0)
            return;
        if (node->st!=NILL)
            node->st->inversiune^=1;
        if (node->dr != NILL)
            node->dr->inversiune^=1;
        node->inversiune=0;
        treapuri*Aux;
        Aux = node->st;
        node->st = node->dr;
        node->dr = Aux;
    }
    void inversiune (treapuri *& node, int i, int j, int maxim)
    {
        if (i == j)
            return;
        int verif = Find_element(node, j+1);
        if (verif != -1 && i>1)
        {
            creste_greutate(node, maxim, j+1);
            creste_greutate(node, maxim, i-1);
            node->st->dr->inversiune ^= 1;
            return;
        }
        if (verif != -1)
        {
            creste_greutate(node, maxim, j+1);
            node->st->inversiune ^= 1;
            return;
        }
        if (i>1)
        {
            creste_greutate(node, maxim, i-1);
            node->dr->inversiune ^=1;
            return;
        }
        node->inversiune ^= 1;
        return;
    }
    void stergere (treapuri *& node, int i, int j, int maxim)
    {
        creste_greutate(node, maxim, j);
        creste_greutate(node, maxim, i);
        if (i==j)
        {
            dr = node->dr;
            st = node->st;
            Unire (st, dr);
            return;
        }
        dr = node->dr;
        st = node->st->st;
        Unire(st, dr);
        return;
    }
    void Unire (treapuri *& stanga, treapuri *& dreapta)
    {
        treapuri *nou = new treapuri(stanga, dreapta, -1, 0, 0, 0);
        root = nou;
        erase_element(root, -1);
    }
    void Recheck (treapuri *& node)
    {
        if (node == NILL)
            return;
        node->subarbore = 1;
        node->subarbore += node->st->subarbore;
        node->subarbore += node->dr->subarbore;
    }
    void creste_greutate (treapuri *& node, int maxim, int poz)
    {
        if (node==NILL)
            return;
        Update(node);
        if (poz == node->st->subarbore+1)
            node->greutate = maxim+1;
        else
        {
            if (poz<=node->st->subarbore)
                creste_greutate(node->st, maxim, poz);
            else creste_greutate(node->dr, maxim, poz-node->st->subarbore-1);
        }
        Balance(node);
    }

    void RightRotate (treapuri *&node)
    {
        Recheck(node);
        treapuri *Aux = node->dr;
        node->dr=Aux->st;
        Aux->st = node;
        node = Aux;
        Recheck(node->st);
        Recheck(node->dr);
        Recheck(node);
    }
    void LeftRotate (treapuri *&node)
    {
        Recheck(node);
        treapuri *Aux = node->st;
        node->st = Aux->dr;
        Aux->dr = node;
        node = Aux;
        Recheck(node->st);
        Recheck(node->dr);
        Recheck(node);
    }
    void Balance (treapuri *&node)
    {
        Recheck(node);
        if (node->st!=NILL && node->st->greutate > node->greutate)
            LeftRotate(node);
        if (node->dr!=NILL && node->dr->greutate > node->greutate)
            RightRotate(node);
    }
    int Find_element (treapuri *&node, int val)
    {
        Update(node);
        if (node == NILL)
            return -1;
        if (node->st->subarbore+1 == val)
            return node->valoare;
        if (node->st->subarbore >= val)
            return Find_element(node->st, val);
        return Find_element(node->dr, val-node->st->subarbore-1);
    }
    void insert_value (treapuri *&nod, int val, int poz)
    {
        Update(nod);
        if (nod == NILL)
        {
            nod = new treapuri (NILL, NILL, val, 1, Random_Generator_Number()+1, 0);
            return;
        }
        if (nod->st->subarbore+1 >= poz)
            insert_value(nod->st, val, poz);
        else insert_value(nod->dr, val, poz-nod->st->subarbore-1);
        Balance(nod);
    }
    void erase_element (treapuri *&node, int val)
    {
        Update(node);
        if (node->valoare > val)
            erase_element(node->st, val);
        else
        {
            if (node->valoare < val) erase_element(node->dr, val);
            else
            {
                if (node->st==NILL && node->dr == NILL)
                {
                    delete node;
                    node = NILL;
                    return;
                }
                if (node->dr!=NILL && node->st!=NILL)
                {
                    if (node->dr->greutate>node->st->greutate)
                        LeftRotate(node), erase_element(node->dr, val);
                    else
                        RightRotate(node), erase_element(node->st, val);
                }
                else
                {
                    if (node->dr!=NILL)
                        RightRotate(node), erase_element(node->st, val);
                    else
                        LeftRotate(node), erase_element(node->dr, val);
                }
            }
        }
        Balance(node);
    }
    void afisare_treap (treapuri *& node)
    {
        if (node == NILL)
            return;
        afisare_treap(node->st);
        fout << node->valoare << " ";
        afisare_treap(node->dr);
    }
};

int main()
{
    Treap *T;
    int maxim = 6666030;
    T = new Treap();
    ifstream fin ("secv8.in");
    int n, useless;
    fin >> n >> useless;
    fin.get();
    while (n--)
    {
        char c;
        c = fin.get();
        if (c == 'I')
        {
            int k, e;
            fin >> k >> e;
            T->insert_value(T->root, e, k);
        }
        if (c == 'A')
        {
            int k;
            fin >> k;
            fout << T->Find_element(T->root, k) << '\n';
        }
        if (c == 'R')
        {
            int i, j;
            fin >> i >> j;
            T->inversiune(T->root, i, j, maxim);
            ++maxim;
        }
        if (c == 'D')
        {
            int i, j;
            fin >> i >> j;
            T->stergere(T->root, i, j, maxim);
            ++maxim;
        }
        fin.get();
    }
    T->afisare_treap(T->root);
    return 0;
}