#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>

#define CharLength 100 // максимальная длина слова

struct struct SkipListElement {
    struct SkipListElement **mass;
    int k;
    char *val;
};

struct struct SkipListElement *InitSkipList(int m)
{
    int i;
    struct SkipListElement *l;
    l=(struct SkipListElement*)malloc(sizeof(struct SkipListElement));
    l->mass = (struct SkipListElement**)malloc(m*sizeof(struct SkipListElement*));
    l->k=0;
    l->val=(char*)malloc(CharLength*sizeof(char));
    for (i=0; i<m; i++) l->mass[i] = 0;
    return l;
}

struct struct SkipListElement* Succ(struct SkipListElement *p)
{
    return (p->mass[0]);
}

void Skip(struct SkipListElement *l, int m, int k, struct SkipListElement **p)
{
    struct struct SkipListElement *x = l;
    int i;
    for (i = m-1; i>=0; i--) {
        while ((x->mass[i])&&(k>x->mass[i]->k)) x = x->mass[i];
        p[i]=x;
    }
}

void Delete(struct SkipListElement *l, int m, int k)
{
    int i;
    struct SkipListElement *x, **p = (struct SkipListElement**)malloc(m*sizeof(struct SkipListElement*));
    Skip(l, m, k, p);
    x=Succ(p[0]);
    for (i=0; ((i<m)&&(p[i]->mass[i]==x)); i++) p[i]->mass[i]=x->mass[i];
    free(x->val);
    free(x->mass);
    free(x);
    free(p);
}

void Insert(struct SkipListElement *l, int m, int k, char *v)
{
    int r, i;
    struct SkipListElement *x, **p = (struct SkipListElement**)malloc(m*sizeof(struct SkipListElement*));
    Skip(l, m, k, p);
    srand((unsigned int)time(0));
    x = InitSkipList(m);
    strncpy(x->val, v, CharLength);
    x->k=k;
    r = rand()*2;
    for (i=0; ((i<m)&&!(r%2)); i++, r/=2) {
        x->mass[i]=p[i]->mass[i];
        p[i]->mass[i]=x;
    }
    free(p);
}

void LookUp(struct SkipListElement *l, int m, int k)
{
    struct SkipListElement **p = (struct SkipListElement**)malloc(m*sizeof(struct SkipListElement*));
    Skip(l, m, k, p);
    printf("%s\n", (Succ(p[0]))->val);
    free(p);
}

void Rank (struct SkipListElement *l, int m, int k)
{
    int i;
    struct SkipListElement *x = l;
    for(i=0; k!=x->k; x=x->mass[0], i++);
    printf("%d\n", i-1);
}

void main()
{
    int i, n, m, k;
    char v[CharLength], a[7];
    struct SkipListElement *l;
    scanf("%d", &n);
    m = log((float)n)/log((float)2) + 1;
    l = InitSkipList(m);
    for (i=0; i<n; i++) {
        scanf("%s", a);
        switch (a[0]) {
            case 'I':
                scanf("%d %s", &k, v);
                Insert(l, m, k, v);
                break;
            default:
                scanf("%d", &k);
                switch (a[0]) {
                    case 'L': LookUp(l, m, k); break;
                    case 'D': Delete(l, m, k); break;
                    case 'R': Rank(l, m, k); break;
                }
        }
    }
}