import java.io.PrintStream;

public class ST {

    private class TreeNode {
        int id;
        String city;
        TreeNode l;
        TreeNode r;
        int N;
        List booklist = new List();

        TreeNode(int id, String city) {
            this.id = id;
            this.city = city;
        }
    }

    private TreeNode head;

    void insertWarehouse(int nodeId, String name) {
        if (searchWarehouse(nodeId) != null) {
            System.out.println("Warehouse with this id already exists.");
        }
        head = insertR(head, new TreeNode(nodeId, name));
        System.out.println("New warehouse added.");
    }

    void insertBookAtWarehouse(int nodeId, int isbn, int copies) {
        TreeNode targetWarehouse = searchWarehouse(nodeId);
        if (targetWarehouse == null){
            System.out.println("Warehouse doesn't exist.");
        } else{
            targetWarehouse.booklist.insert(new Node(new BookInfo(isbn, copies)));
        }
    }

    void removeWarehouse(int nodeId) {
        head = removeWarehouse(head, nodeId);
    }

    private TreeNode removeWarehouse(TreeNode node, int nodeId) {
        if(node == null) return null;
        if(nodeId < node.id){
            node.l = removeWarehouse(node.l, nodeId);
        }
        else if(nodeId > node.id){
            node.r = removeWarehouse(node.r , nodeId);
        }
        else{
            node = joinTree(node.l, node.r);
            if(node!=null)
                node.N--;
        }
        return node;
    }

    private TreeNode joinTree(TreeNode left, TreeNode right){
        if(left == null)
            return right;
        if(right == null)
            return left;
        int N = left.N + right.N;
        if(Math.random() * N < left.N){
            left.r = joinTree(left.r, right);
            return left;
        }
        else{
            right.l = joinTree(left, right.l);
            return right;
        }
    }

    void removeBook(int nodeId, int isbn) {
        TreeNode targetWarehouse = searchWarehouse(nodeId);
        if(targetWarehouse==null){
            System.out.println("Warehouse doesn't exist.");
        }
        else{
            Node book = targetWarehouse.booklist.getBook(isbn);
            if (book != null) {
                targetWarehouse.booklist.remove(book);
            } else {
                System.out.println("Book doesn't exist in warehouse.");
            }
        }
    }

    void searchByWarehouse(int nodeId) {
        TreeNode cursor = head;
        while(cursor != null){
            if(nodeId == cursor.id){
                cursor.booklist.print(System.out);
                return;
            }
            cursor = nodeId < cursor.id ? cursor.l : cursor.r;
        }
    }

    void searchBookInWarehouse(int nodeId, int isbn) {
        TreeNode toCheck = searchWarehouse(nodeId);

        if(toCheck == null){
            System.out.println("Warehouse not found!");
        } else {
            Node book = toCheck.booklist.getBook(isbn);
            if (book == null) {
                System.out.println("Book not found in warehouse!");
            } else {
                System.out.println("Book found: " + book.getInfo().toString());
            }
        }
    }

    void searchBook(int isbn) {
        searchBook(head, isbn);
    }

    private void searchBook(TreeNode node, int isbn) {
        if (node == null) return;
        Node book = node.booklist.getBook(isbn);
        if (book != null) {
            System.out.println("Book found in warehouse " + node.id + ": " + book.getInfo().toString());
        }
        searchBook(node.r, isbn);
        searchBook(node.l, isbn);
    }

    void printΤree(PrintStream stream) {
        printΤree(head, stream);
    }

    private void printΤree(TreeNode node, PrintStream stream) {
        if (node == null) return;
        System.out.println("Warehouse " + node.id + " (" + node.city  +"):");
        node.booklist.print(stream);
        printΤree(node.l, stream);
        printΤree(node.r, stream);
    }

    private TreeNode searchWarehouse(int nodeId){
        TreeNode cursor = head;
        while(cursor != null){
            if(nodeId == cursor.id){
                return cursor;
            }
            cursor = nodeId < cursor.id ? cursor.l : cursor.r;
        }
        return null;
    }

    TreeNode rotR(TreeNode h){ //rotate right
        TreeNode x = h.l;
        h.l=x.r;
        x.r=h;
        return x;
    }

    TreeNode rotL(TreeNode h){ //rotate left
        TreeNode x= h.r;
        h.r=x.l;
        x.l=h;
        return x;
    }

    private TreeNode insertR(TreeNode parent, TreeNode current) {
        if (parent == null) {
            return current;
        }
        if(Math.random()*(parent.N + 1)<1) {
            return insertS(parent, current);
        }
        if(current.id < parent.id){
            parent.l = insertR(parent.l , current);
        }
        else{
            parent.r = insertR(parent.r , current);
        }
        parent.N++;
        return parent;
    }

    private TreeNode insertS(TreeNode parent, TreeNode current){
        if (parent == null) {
            return current;
        }
        if(current.id < parent.id){
            parent.l = insertS(parent.l, current);
            parent = rotR(parent);
        }
        else{
            parent.r = insertS(parent.r, current);
            parent = rotL(parent);
        }
        parent.N++;
        return parent;
    }

}