#include <stdio.h>
#include <stdlib.h>

int a[2][10000], a_size;

struct tree {
    int key, value, height;
    struct tree *right, *left;
}tree;

int height(struct tree *h) {
    if (h) {
        return h->height;
    }
    else {
        return 0;
    }
}

int maximum(int a, int b) {
    if (a > b) {
        return a;
    }
    else {
        return b;
    }
}

struct tree *single_in_left(struct tree *k) {
    struct tree *temp;
    temp = k->left;
    k->left = temp->right;
    temp->right = k;
    k->height = maximum(height(k->left), height(k->right)) + 1;
    temp->height = maximum(height(temp->left), k->height) + 1;
    return temp;
}

struct tree *single_in_right(struct tree *k1) {
    struct tree *temp;
    temp = k1->right;
    k1->right = temp->left;
    temp->left = k1;
    k1->height = maximum(height(k1->left), height(k1->right)) + 1;
    temp->height = maximum(height(temp->right), k1->height) + 1;
    return temp;
}

struct tree *double_in_left(struct tree *k2) {
    k2->left = single_in_right(k2->left);
    k2 = single_in_left(k2);
    return k2;
}

struct tree *double_in_right(struct tree *k3) {
    k3->right = single_in_left(k3->right);
    k3 = single_in_right(k3);
    return k3;
}

struct tree *ideal_balance(struct tree *head5, int key) {
    if ((!head5->left) && (!head5->right)) {
        head5->height = 1;
    }
    else if (!head5->right) {
        head5->height = head5->left->height + 1;
    }
    else if (!head5->left) {
        head5->height = head5->right->height + 1;
    }
    else {
        if (head5->left->height > head5->right->height) {
            head5->height = head5->left->height + 1;
        }
        else {
            head5->height = head5->right->height + 1;
        }
    }
    if ((height(head5->left) - height(head5->right)) == 2) {
        if (key < head5->left->key) {
            head5 = single_in_left(head5);
        }
        else {
            head5 = double_in_left(head5);
        }
    }
    if ((height(head5->right) - height(head5->left)) == 2) {
        if (key > head5->left->key) {
            head5 = single_in_right(head5);
        }
        else {
            head5 = double_in_right(head5);
        }
    }
    return head5;
}

struct tree *add(struct tree *head4, int value, int key) {
    if (head4 == NULL) {
        head4 = malloc(sizeof(struct tree *));
        head4->right = NULL;
        head4->left = NULL;
        head4->key = key;
        head4->value = value;
        head4->height = 1;
    }
    else if(head4->key>key){
        head4->left = add(head4->left, value, key);
        ideal_balance(head4, key);
    }
    else if (head4->key < key) {
        head4->right = add(head4->right, value, key);
        ideal_balance(head4, key);
    }
    else {
        head4->value = value;
        head4->height = maximum(height(head4->left), height(head4->right)) + 1;
    }
    return head4;
}

void search(struct tree* head3, int key) {
    if (!head3) {
        return NULL;
    }
    if (head3->key == key) {
        a[0][a_size] = key;
        a[1][a_size] = head3->value;
        a_size++;
    }
    else if (head3->key > key) {
        search(head3->left, key);
    }
    else {
        search(head3->right, key);
    }
}

struct tree *min_in_right(struct tree *t) {
    if (!t->left) {
        return t;
    }
    t->left = min_in_right(t->left);
}

struct tree *del_min_in_right(struct tree *head2) {
    if (!head2) {
        return NULL;
    }
    else {
        if (!head2->left) {
            return head2->right;
        }
        head2->left = del_min_in_right(head2->left);
    }
}

struct tree *del(struct tree* head1, int key) {
    if (!head1) {
        return NULL;
    }
    else if (key < head1->key) {
        head1->left = del(head1->left, key);

    }
    else if (key > head1->key) {
        head1->right = del(head1->right, key);
    }
    else {
        struct tree *min;
        if (!head1->right) {
            return head1->left;
        }
        min = min_in_right(head1->right);
        min->right = del_min_in_right(min->right);
        min->left = head1->left;
        ideal_balance(min, key);
        return min;
    }
    ideal_balance(head1, head1->key);
    return head1;
}

void delete_all(struct tree *head) {
    if (head) {
        delete_all(head->left);
        delete_all(head->right);
        free(head);
    }
    return NULL;
}

int main(void) {
    char op='F';
    int key=0, val=0;
    struct tree *head=NULL;
    scanf("%c", &op);
    while (op != 'F') {
        if (op == 'A') {
            scanf("%d %d", &key, &val);
            head = add(head, val, key);
        }
        else if (op == 'S') {
            scanf("%d", &key);
            search(head, key);
        }
        else if (op == 'D') {
            scanf("%d", &key);
            head = del(head, key);
        }
        scanf("%c", &op);
    }

    for (int i = 0; i < a_size; i++) {
        printf("%d %d\n", a[0][i], a[1][i]);
    }
    delete_all(head);
    return 0;
}