sfajkd

import java.io.IOException;
import java.util.StringTokenizer;


class Node {
    public String cartao;
    public int saldo;
    public Node left;
    public Node right;
    public float priority;

    Node(String cartao, int saldo) {
        this.cartao = cartao;
        this.saldo = saldo;
        left = null;
        right = null;
        /*this.priority = Math.random();*/
        this.priority = (float)(((int)(Math.random() * 100)) * 0.01);
    }

    Node(String cartao, int saldo, Node l, Node r) {
        this.cartao = cartao;
        this.saldo = saldo;
        left = l;
        right = r;
        /*this.priority = Math.random();*/
        this.priority = (float)(((int)(Math.random() * 100)) * 0.01);

    }

    int compareTo(String cartao) {
        return this.cartao.compareTo(cartao);
    }

    int compareTo(Node otherNode) {
        return this.compareTo(otherNode.cartao);
    }
}


class TREAP{

    protected Node root = null;

    public TREAP() {
        root = null;
    }

    public TREAP (Node no) {
        root = no;
    }

    public TREAP(String cartao, int saldo) {
        root = new Node(cartao, saldo);
    }


    public Node get(Node no) {

        return this.get(no.cartao);
    }

    public Node get(String cartao) {
        Node no = root;
        while (no != null) {
            if (no.compareTo(cartao) == 0) {
                return no;
            }
            no = ((no.compareTo(cartao) > 0) ? no.left : no.right);
        }
        return null;
    }


    Node rightrotation (Node no){
        Node k = no.left;
        Node j = k.right;

        k.right = no;
        no.left = j;

        return k;
    }

    Node leftrotation (Node no){
        Node j = no.right;
        Node k = j.left;

        j.left = no;
        no.right = k;

        return j;
    }


    public void add(String cartao, int saldo) {
        root = add(cartao, saldo, root);
        return;
    }

    public Node add(String cartao, int valor, Node no) {

        if (no == null) {
            return new Node (cartao, valor);
        }

        if (no.compareTo(cartao) == 0){
            no.saldo += valor;
        }

        else{
            if (no.compareTo(cartao) > 0){
                no.left = add(cartao, valor, no.left);

                if (no.left.priority > no.priority)
                    no = rightrotation(no);
            }

            else{
                no.right = add(cartao, valor, no.right);

                if (no.right.priority > no.priority)
                    no = leftrotation(no);
        }
    }
        return no;
    }


    public void remove(Node no) {
        remove(no.cartao);
    }

    public void remove(String cartao){
        root = remove(root, cartao);
    }

    public Node remove (Node no, String cartao){

        if (no == null)
            return null;

        if (no.compareTo(cartao) == 0) {
            if (no.left == null) {
                return no.right;
            } else if (no.right == null) {
                return no.left;
            } else {
                if(no.left.priority < no.right.priority){
                    no = leftrotation(no);
                    no.left = remove(no.left, cartao);
                }
                else{
                    no = rightrotation(no);
                    no.right = remove(no.right, cartao);
                }
            }
        } else {
            if (no.compareTo(cartao) > 0) {
                no.left = remove(no.left, cartao);
            } else {
                no.right = remove(no.right, cartao);
            }
        }


        return no;
    }

    void printInOrder(){
        printInOrder(root);
    }

    void printInOrder(Node no){
        if (no==null)
            return;
        printInOrder(no.left);
        System.out.println(no.cartao + " SALDO " + no.saldo);
        printInOrder(no.right);
    }

}


public class FichaTP1_D {

    static String readLn (int maxLg){
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";
        try {
            while (lg < maxLg){
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e){
            return (null);
        }
        if ((car < 0) && (lg == 0)) return (null);
        return (new String (lin, 0, lg));
    }

    public static void main(String[] args) {

        String input, comando;
        int contribuinte, valor;
        String cartao;
    StringTokenizer st;

        TREAP tree = new TREAP();
        do {
            input = readLn(200);
            st= new StringTokenizer(input.trim());
            comando = st.nextToken();
            if (comando.equals("UPDATE")){
                cartao = new String(st.nextToken());
                valor = Integer.parseInt(st.nextToken());
                tree.add (cartao, valor);
            }
            else if (comando.equals("SALDO")){
                cartao = new String(st.nextToken());
                Node no = tree.get(cartao);
                if (no==null)
                    System.out.println(cartao + " INEXISTENTE");
                else
                    System.out.println(cartao + " SALDO " + no.saldo);
            }
            else if (comando.equals("REMOVE")){
                cartao = new String(st.nextToken());
                tree.remove(cartao);
            }
            else if (comando.equals("IMPRIME")){
                tree.printInOrder();
            }
            else if (comando.equals("TERMINA"))
                return;
        } while (true);
    }

}