#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;

const int RAND = 10000000, INF = 0x3f3f3f3f;

struct Treap
{
    int Key, Priority, Min, Max, MinDif, Size;
    Treap *Left, *Right;

    Treap() {}
    Treap(int Key, int Priority, int Min, int Max, int MinDif, int Size, Treap *Left, Treap *Right)
    {
        this -> Key = Key;
        this -> Priority = Priority;
        this -> Min = Min;
        this -> Max = Max;
        this -> MinDif = MinDif;
        this -> Size = Size;
        this -> Left = Left;
        this -> Right = Right;
    }
};

Treap *T, *NIL;

void Initialize()
{
    srand(time(NULL));
    T = NIL = new Treap(0, 0, INF, -INF, INF, 0, NULL, NULL);
    NIL -> Left = NIL -> Right = NIL;
}

void Update(Treap *T)
{
    T -> Size = T -> Left -> Size + T -> Right -> Size + 1;
    T -> Min = min(T -> Left -> Min, T -> Key);
    T -> Max = max(T -> Key, T -> Right -> Max);
    T -> MinDif = min(T -> Left -> MinDif, T -> Right -> MinDif);
    T -> MinDif = min(T -> MinDif, min(T -> Key - T -> Left -> Max, T -> Right -> Min - T -> Key));
}

void RotateLeft(Treap *&T)
{
    Treap *Aux = T;
    Aux->Right = T->Right->Left;
    T=T->Right;
    T->Left=Aux;

    Update(T -> Left);
    Update(T);
}

void RotateRight(Treap *&T)
{
    Treap *Aux = T;
    Aux->Left = T->Left->Right;
    T=T->Left;
    T->Right=Aux;

    Update(T -> Right);
    Update(T);
}

void Balance(Treap *&T)
{
    if(T -> Left -> Priority > T -> Priority) RotateRight(T);
    else if(T -> Right -> Priority > T -> Priority) RotateLeft(T);
}

void Insert(Treap *&T, int Key, int Priority)
{
    if(T == NIL)
    {
        T = new Treap(Key, Priority, Key, Key, INF, 1, NIL, NIL);
        return ;
    }

    if(Key < T -> Key) Insert(T -> Left, Key, Priority);
    else if(Key > T -> Key) Insert(T -> Right, Key, Priority);

    Balance(T);
    Update(T);
}

void Erase(Treap *&T, int Key)
{
    if(T == NIL) return ;

    if(Key < T -> Key) Erase(T -> Left, Key);
    else if(Key > T -> Key) Erase(T -> Right, Key);
    else
    {
        if(T -> Left == NIL && T -> Right == NIL)
        {
            delete T;
            T = NIL;
            return ;
        }

        if(T -> Left -> Priority > T -> Right -> Priority)
            RotateRight(T), Erase(T -> Right, Key);
        else
            RotateLeft(T), Erase(T -> Left, Key);
    }

    Update(T);
}

int Search(Treap *T, int Key)
{
    if(T == NIL) return 0;
    if(T -> Key == Key) return 1;
    if(Key < T -> Key) return Search(T -> Left, Key);
    return Search(T -> Right, Key);
}

char Query[20];

int main()
{
    Initialize();
    freopen("zeap.in", "r", stdin);
    freopen("zeap.out", "w", stdout);

    fgets(Query, 20, stdin);
    while(!feof(stdin))
    {
        if(Query[0] == 'M')
        {
            if(Query[1] == 'A') printf("%i\n", T -> Size >= 2 ? T -> Max - T -> Min : -1);
            else printf("%i\n", T -> Size >= 2 ? T -> MinDif : -1);
        }else
        {
            int X = 0, N = strlen(Query) - 1;
            for(int i = 2; i < N; ++ i) X = X * 10 + Query[i] - '0';
            int Res = Search(T, X);
            if(Query[0] == 'I' && Res == 0) Insert(T, X, rand() % RAND + 1);
            if(Query[0] == 'S')
            {
                if(Res == 0) printf("-1\n");
                else Erase(T, X);
            }
            if(Query[0] == 'C') printf("%i\n", Res);
        }

        fgets(Query, 20, stdin);
    }
}