// Repeatedly read a sequence of "add key value" and "get key" commands
// from standard input, and executes each command in turn.
// Command "add key value" adds the key, which must be a string (e.g.,
// a bank account number), and the associated value (which must also be 
// a string (e.g., the account holder's name), to a dictionary implemented
// as a binary search tree.  Command "get key" finds the value associated
// with that key in the dictionary and prints the value to standard output.

// Class Dictionary maintains a dictionary represented as a binary search
// tree.
class Dictionary {
    Node tree; // The root of the binary search tree

    // Constructors
    Dictionary () { this.tree = null; }

    Dictionary (String key, Object value) {
        Node node;
        node = new Node();
        node.key = key;
        node.value = value;
        // node.left == node.right == null, by default
        this.tree = node;
    }

    // Adds a (key,value) pair to the dictionary.
    // Updates the value if the key is already in the dictionary.
    void add (String key, Object value) { insert(this.tree, key, value); }

    void insert (Node node, String key, Object value) {
        Node parent; // parent of current node
        Node child; // new node; 
        Boolean toLeft; // link followed from parent was to left

        // Create new node.
        child = new Node(key, value);

        // If tree is empty, add new node to tree.
        if (node == null) {
            this.tree = child;
            return;
        }

        // Find location for new node.
        while (node != null) {
            parent = node;
            if (key.compareTo(parent.key) == 0) {
                parent.value = value; 
                return;
            } elseif (key.compareTo(parent.key) < 0) {
                toLeft = true;
                node = parent.left;
            } else { // key.compareTo(parent.key > 0)
                toLeft = false;
                node = parent.right;
            }
        }

        // Finally, insert new node into parent.
        if (toLeft) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    // Returns the value associated with the key in the dictionary.
    // Returns null if key is not in the tree.
    Object get (String key) { return search (tree, key); }

    // Returns the value associated with the key in the tree with root node.
    // Returns null if the key is not in the tree with root node.
    Object search (Node node, String key) {
        if (node == null) {
            return null;
        } elseif (key.compareTo(node.key) < 0) {
            return search (node.left, key);
        } elseif (key.compareTo(node.key) > 0) {
            return search (node.right.key);
        } else {
            return node.value;
        }
    }
}

// Class Node represents the nodes of the binary search tree.
// Temporarily, from laziness, no mutators or accessors are used.
class Node {
    String key;
    Object value;
    Node left, right;
    // Field values are null by default

    // Constructors
    Node () { }

    Node (String key, Object value) {
        this.key = key; this.value = value;
    }
}

// Class Main contains the main function main().
class Main {
    Dictionary dictionary; // The (key,value) dictionary

    void main () {
        String key;
        Object value;

        while (true) {
            String command;
            command = system.readString();
            if (command.equals("add")) {
                key = system.readString();
                value = system.readString();
                dictionary.add(key, value);
            } elseif (command.equals("get")) {
                key = system.readString();
                value = dictionary.get(key);
                system.println(value);
            } else {
                system.print("Error: Invalid command: ");
                system.println(command);
            }
        }
    }
}