import java.util.ArrayList;

enum Color {
    RED,
    BLACK,
}

class RBTree {
    private class Element {
        int value;
        Element right, left, parent;
        Color color;

        Element(int v, Color color, Element parent) {
            value = v;
            this.parent = parent;
            right = null;
            left = null;
            this.color = color;
        }

        public String toString() {
            return (color == Color.RED ? "R" : "B") + "(" + value + ")";
        }

    }

    private Element root;
    private int tempLayer;

    RBTree() {
        root = null;
    }

    private Element parentOf(int key) {
        Element current = root;

        while(current != null) {
            if(current.right != null)
                if(current.right.value == key)
                    return current;
            if(current.left != null)
                if(current.left.value == key)
                    return current;

            if(key < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }

    private void leftRotate(Element x) {
        Element y = x.right;
        x.right = y.left;

        if(y.left != null) {
            y.left.parent = x;
        }
        y.parent = x.parent;

        if(x.parent == null) {
            root = y;
        } else if(x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }

        y.left = x;
        x.parent = y;
    }

    private void rightRotate(Element x) {
        Element y = x.left;
        x.left = y.right;

        if(y.right != null) {
            y.right.parent = x;
        }
        y.parent = x.parent;

        if(x.parent == null) {
            root = y;
        } else if(x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }

        y.right = x;
        x.parent = y;
    }

    private Element treePut(int key) {
        if(root == null) {
            root = new Element(key, Color.BLACK, null);
            return root;
        }
        Element current = root;

        while(true) {
            if(key < current.value) {
                if(current.left == null) {
                    current.left = new Element(key, Color.RED, null);
                    current = current.left;
                    break;
                }
                current = current.left;
            } else {
                if(current.right == null) {
                    current.right = new Element(key, Color.RED, null);
                    current = current.right;
                    break;
                }
                current = current.right;
            }
        }
        current.parent = parentOf(current.value);
        return current;
    }

    void add(int key) {
       Element current = treePut(key); // standardowe dodawanie do drzewa binarnego

       // to masz od ikłilsa - obracanie tak żeby było tyle samo czarnych po 2 stronach i nie było 2
       // czerwonych obok siebie
       while(current != root && current.parent.color == Color.RED) {
            if(current.parent == current.parent.parent.left) {
                Element y = current.parent.parent.right;
                if(y.color == Color.RED) {
                    current.parent.color = Color.BLACK;
                    y.color = Color.BLACK;
                    current.parent.parent.color = Color.RED;
                    current = current.parent.parent;
                } else {
                    if(current == current.parent.right) {
                        current = current.parent;
                        leftRotate(current);
                    }
                    current.parent.color = Color.BLACK;
                    current.parent.parent.color = Color.RED;
                    rightRotate(current.parent.parent);
                }
            }
            // -------------------------------------------------------------
            if(current.parent == current.parent.parent.right) {
                Element y = current.parent.parent.left;
                if(y.color == Color.RED) {
                    current.parent.color = Color.BLACK;
                    y.color = Color.BLACK;
                    current.parent.parent.color = Color.RED;
                    current = current.parent.parent;
                } else {
                    if(current == current.parent.left) {
                        current = current.parent;
                        leftRotate(current);
                    }
                    current.parent.color = Color.BLACK;
                    current.parent.parent.color = Color.RED;
                    rightRotate(current.parent.parent);
                }
            }
            root.color = Color.BLACK;
        }
    }

    void inorder_show() {
        System.out.print("In-order: ");
        inorder_show(root);
        System.out.println();
    }

    void preorder_show() {
        System.out.print("Pre-order: ");
        preorder_show(root);
        System.out.println();
    }

    void postorder_show() {
        System.out.print("Post-order: ");
        postorder_show(root);
        System.out.println();
    }

    private void inorder_show(Element current) {
        if(current != null) {
            inorder_show(current.left);

            System.out.print(current + " ");

            inorder_show(current.right);
        }
    }

    private void preorder_show(Element current) {
        if(current != null) {
            System.out.print(current + " ");

            preorder_show(current.left);
            preorder_show(current.right);
        }
    }

    private void postorder_show(Element current) {
        if(current != null) {
            postorder_show(current.left);
            postorder_show(current.right);

            System.out.print(current + " ");
        }
    }

    void rowprint() {
         ArrayList<ArrayList<Element>> elements = new ArrayList<>();
         rowprint(elements, root, 0);

         for(ArrayList<Element> row: elements) {
             for(Element element: row) {
                 System.out.print(element + " ");
             }
             System.out.println();
         }
    }

    private void rowprint(ArrayList<ArrayList<Element>> elements, Element current, int layer) {
        if(current != null) {
            if(elements.size() == layer) {
                elements.add(new ArrayList<>());
            }
            elements.get(layer).add(current);
            rowprint(elements, current.left, layer+1);
            rowprint(elements, current.right, layer+1);
        }
    }

    boolean find(int key) {
        Element current = root;
        System.out.print("Tree contains " + key + " ? - ");

        while(current != null) {
            if(current.value == key)
                return true;

            if(key < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    int nodeCount() {
        return nodeCount(root);
    }

    private int nodeCount(Element current) {
        if(current != null) {
            return 1 + nodeCount(current.left) + nodeCount(current.right);
        }
        return 0;
    }

    int height() {
        tempLayer = 0;
        height(root, 0);
        return tempLayer;
    }

    private void height(Element current, int layer) {
        if(current != null) {
            height(current.left, layer + 1);
            height(current.right, layer + 1);

            if (tempLayer < layer) tempLayer = layer;
        }
    }
}