Ideone.com

fork download

copy

public class Main
{
    public static void main(String[] args)
    {
        java.util.Random r = new java.util.Random();
        Tree tree = new Tree();
        int[] a = seq(256);
        sfl(a, r);
        for (int i : a)
        {
            tree.add(i);
        }
        for (int i = 0; i < a.length - 15; i++)
        {
            tree.remove(a[i]);
        }
        tree.print();
    }
 
    static int[] rnd(int c, java.util.Random r)
    {
        int[] a = new int[c];
        for (int i = 0; i < c; i++)
        {
            a[i] = r.nextInt(c);
        }
        return a;
    }
 
    static int[] seq(int c)
    {
        int[] a = new int[c];
        for (int i = 0; i < c; i++)
        {
            a[i] = i;
        }
        return a;
    }
 
    static void rev(int a[])
    {
        int i = 0;
        int j = a.length - 1;
        while (i < j)
        {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
        }
    }
 
    static void sfl(int a[], java.util.Random r)
    {
        for (int i = a.length; 0 < i; i--)
        {
            int j = r.nextInt(i);
            int t = a[j];
            a[j] = a[i - 1];
            a[i - 1] = t;
        }
    }
}
 
class Tree
{
    Node root;
    Node nullNode;
 
    public Tree()
    {
        nullNode = new Node(0, null, null, Color.black);
        root = nullNode;
    }
 
    public void add(int value)
    {
        Node node = new Node(value, nullNode, nullNode, Color.red);
        Adder adder = new Adder(node);
        adder.add();
    }
 
    public void remove(int value)
    {
        Remover remover = new Remover(value);
        remover.remove();
    }
 
    public void print()
    {
        Printer printer = new Printer();
        printer.print();
    }
 
    enum Color
    {
        red,
        black
    }
 
    class Node
    {
        int value;
        Node left;
        Node right;
        Color color;
 
        Node(int value, Node left, Node right, Color color)
        {
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }
    }
 
    class Remover
    {
        int removeValue;
        Node resNode;
        int minValue;
        boolean balanced;
        boolean removed;
 
        Remover(int removeValue)
        {
            this.removeValue = removeValue;
            this.resNode = nullNode;
            this.balanced = false;
            this.removed = false;
        }
 
        void remove()
        {
            if (root == nullNode)
            {
            }
            else
            {
                remove(root);
                if (removed)
                {
                    root = resNode;
                }
            }
        }
 
        void remove(Node node)
        {
            if (removeValue < node.value)
            {
                if (node.left == nullNode)
                {
                    removed = false;
                    balanced = true;
                }
                else
                {
                    remove(node.left);
                    if (removed)
                    {
                        node.left = resNode;
                        balanceL(node);
                    }
                }
            }
            else
            {
                if (node.value < removeValue)
                {
                    if (node.right == nullNode)
                    {
                        removed = false;
                        balanced = true;
                    }
                    else
                    {
                        remove(node.right);
                        if (removed)
                        {
                            node.right = resNode;
                            balanceR(node);
                        }
                    }
                }
                else
                {
                    removed = true;
                    if (node.left == nullNode)
                    {
                        if (node.right == nullNode)
                        {
                            resNode = nullNode;
                            balanced = node.color == Color.red;
                        }
                        else
                        {
                            resNode = node.right;
                            resNode.color = Color.black;
                            balanced = true;
                        }
                    }
                    else
                    {
                        if (node.right == nullNode)
                        {
                            resNode = node.left;
                            resNode.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            removeMin(node.right);
                            node.right = resNode;
                            node.value = minValue;
                            balanceR(node);
                        }
                    }
                }
            }
        }
 
        void removeMin(Node node)
        {
            if (node.left == nullNode)
            {
                minValue = node.value;
                resNode = node.right;
                balanced = node.color == Color.red;
            }
            else
            {
                removeMin(node.left);
                node.left = resNode;
                balanceL(node);
            }
        }
 
        void balanceR(Node a)
        {
            if (balanced)
            {
                resNode = a;
            }
            else
            {
                Node b = a.left;
                Node c = b.right;
                Node d = b.left;
                if (a.color == Color.black)
                {
                    if (b.color == Color.red)
                    {
                        Node e = c.right;
                        Node f = c.left;
                        if (e.color == Color.red)
                        {
                            resNode = rotateR3(a);
                            e.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            if (f.color == Color.red)
                            {
                                resNode = rotateR2(a);
                                f.color = Color.black;
                                balanced = true;
                            }
                            else
                            {
                                resNode = rotateR1(a);
                                b.color = Color.black;
                                c.color = Color.red;
                                balanced = true;
                            }
                        }
                    }
                    else
                    {
                        if (c.color == Color.red)
                        {
                            resNode = rotateR2(a);
                            c.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            if (d.color == Color.red)
                            {
                                resNode = rotateR1(a);
                                d.color = Color.black;
                                balanced = true;
                            }
                            else
                            {
                                resNode = a;
                                b.color = Color.red;
                            }
                        }
                    }
                }
                else
                {
                    if (c.color == Color.red)
                    {
                        resNode = rotateR2(a);
                        a.color = Color.black;
                        balanced = true;
                    }
                    else
                    {
                        if (d.color == Color.red)
                        {
                            resNode = rotateR1(a);
                            a.color = Color.black;
                            b.color = Color.red;
                            d.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            resNode = a;
                            a.color = Color.black;
                            b.color = Color.red;
                            balanced = true;
                        }
                    }
                }
            }
        }
 
        Node rotateR1(Node a)
        {
            Node b = a.left;
            a.left = b.right;
            b.right = a;
            return b;
        }
 
        Node rotateR2(Node a)
        {
            Node b = a.left;
            Node c = b.right;
            b.right = c.left;
            a.left = c.right;
            c.left = b;
            c.right = a;
            return c;
        }
 
        Node rotateR3(Node a)
        {
            Node b = a.left;
            Node c = b.right;
            Node e = c.right;
            c.right = e.left;
            a.left = e.right;
            e.left = b;
            e.right = a;
            return e;
        }
 
        void balanceL(Node a)
        {
            if (balanced)
            {
                resNode = a;
            }
            else
            {
                Node b = a.right;
                Node c = b.left;
                Node d = b.right;
                if (a.color == Color.black)
                {
                    if (b.color == Color.red)
                    {
                        Node e = c.left;
                        Node f = c.right;
                        if (e.color == Color.red)
                        {
                            resNode = rotateL3(a);
                            e.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            if (f.color == Color.red)
                            {
                                resNode = rotateL2(a);
                                f.color = Color.black;
                                balanced = true;
                            }
                            else
                            {
                                resNode = rotateL1(a);
                                b.color = Color.black;
                                c.color = Color.red;
                                balanced = true;
                            }
                        }
                    }
                    else
                    {
                        if (c.color == Color.red)
                        {
                            resNode = rotateL2(a);
                            c.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            if (d.color == Color.red)
                            {
                                resNode = rotateL1(a);
                                d.color = Color.black;
                                balanced = true;
                            }
                            else
                            {
                                resNode = a;
                                b.color = Color.red;
                            }
                        }
                    }
                }
                else
                {
                    if (c.color == Color.red)
                    {
                        resNode = rotateL2(a);
                        a.color = Color.black;
                        balanced = true;
                    }
                    else
                    {
                        if (d.color == Color.red)
                        {
                            resNode = rotateL1(a);
                            a.color = Color.black;
                            b.color = Color.red;
                            d.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            resNode = a;
                            a.color = Color.black;
                            b.color = Color.red;
                            balanced = true;
                        }
                    }
                }
            }
        }
 
        Node rotateL1(Node a)
        {
            Node b = a.right;
            a.right = b.left;
            b.left = a;
            return b;
        }
 
        Node rotateL2(Node a)
        {
            Node b = a.right;
            Node c = b.left;
            b.left = c.right;
            c.right = b;
            a.right = c.left;
            c.left = a;
            return c;
        }
 
        Node rotateL3(Node a)
        {
            Node b = a.right;
            Node c = b.left;
            Node e = c.left;
            c.left = e.right;
            e.right = b;
            a.right = e.left;
            e.left = a;
            return e;
        }        
    }
 
    class Adder
    {
        Node addNode;
        Node resNode;
        boolean balanced;
        boolean added;
 
        Adder(Node addNode)
        {
            this.addNode = addNode;
            this.resNode = nullNode;
            this.balanced = false;
            this.added = false;
        }
 
        void add()
        {
            if (root == nullNode)
            {
                root = addNode;
            }
            else
            {
                add(root);
                if (added)
                {
                    root = resNode;
                    root.color = Color.black;
                }
            }
        }
 
        Node rotateR1(Node a)
        {
            Node b = a.left;
            a.left = b.right;
            b.right = a;
            return b;
        }
 
        Node rotateR2(Node a)
        {
            Node b = a.left;
            Node e = b.right;
            a.left = e.right;
            b.right = e.left;
            e.right = a;
            e.left = b;
            return e;
        }
 
        Node rotateL1(Node a)
        {
            Node b = a.right;
            a.right = b.left;
            b.left = a;
            return b;
        }
 
        Node rotateL2(Node a)
        {
            Node b = a.right;
            Node e = b.left;
            a.right = e.left;
            b.left = e.right;
            e.left = a;
            e.right = b;
            return e;
        }
 
        void balanceL(Node a)
        {
            if (balanced)
            {
                resNode = a;
            }
            else
            {
                if (a.color == Color.black)
                {
                    Node b = a.left;
                    Node c = a.right;
                    Node d = b.left;
                    Node e = b.right;
                    if (c.color == Color.black)
                    {
                        if (e.color == Color.red)
                        {
                            resNode = rotateR2(a);
                            a.color = Color.red;
                            e.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            if (d.color == Color.red)
                            {
                                resNode = rotateR1(a);
                                a.color = Color.red;
                                b.color = Color.black;
                                balanced = true;
                            }
                            else
                            {
                                resNode = a;
                                balanced = true;
                            }
                        }
                    }
                    else
                    {
                        if (e.color == Color.red || d.color == Color.red)
                        {
                            resNode = a;
                            a.color = Color.red;
                            b.color = Color.black;
                            c.color = Color.black;
                        }
                        else
                        {
                            resNode = a;
                            balanced = true;
                        }
                    }
                }
                else
                {
                    resNode = a;
                }
            }
        }
 
        void balanceR(Node a)
        {
            if (balanced)
            {
                resNode = a;
            }
            else
            {
                if (a.color == Color.black)
                {
                    Node b = a.right;
                    Node c = a.left;
                    Node d = b.right;
                    Node e = b.left;
                    if (c.color == Color.black)
                    {
                        if (e.color == Color.red)
                        {
                            resNode = rotateL2(a);
                            a.color = Color.red;
                            e.color = Color.black;
                            balanced = true;
                        }
                        else
                        {
                            if (d.color == Color.red)
                            {
                                resNode = rotateL1(a);
                                a.color = Color.red;
                                b.color = Color.black;
                                balanced = true;
                            }
                            else
                            {
                                resNode = a;
                                balanced = true;
                            }
                        }
                    }
                    else
                    {
                        if (e.color == Color.red || d.color == Color.red)
                        {
                            resNode = a;
                            a.color = Color.red;
                            b.color = Color.black;
                            c.color = Color.black;
                        }
                        else
                        {
                            resNode = a;
                            balanced = true;
                        }
                    }
                }
                else
                {
                    resNode = a;
                }
            }        
        }
 
        void add(Node node)
        {
            if (addNode.value < node.value)
            {
                if (node.left == nullNode)
                {
                    node.left = addNode;
                    balanced = node.color == Color.black;
                    resNode = node;
                    added = true;
                }
                else
                {
                    add(node.left);
                    if (added)
                    {
                        node.left = resNode;
                        balanceL(node);
                    }
                }
            }
            else if (node.value < addNode.value)
            {
                if (node.right == nullNode)
                {
                    node.right = addNode;
                    balanced = node.color == Color.black;
                    resNode = node;
                    added = true;
                }
                else
                {
                    add(node.right);
                    if (added)
                    {
                        node.right = resNode;
                        balanceR(node);
                    }
                }
            }
            else
            {
                added = false;
                balanced = true;
            }
        }
    }
 
    class Printer
    {
        String indent;
 
        Printer()
        {
            indent = "";
        }
 
        void print()
        {
            if (root == nullNode)
            {
                System.out.println("empty");
            }
            else
            {
                indent = "";
                print(root);
            }
        }
 
        void print(Node node)
        {
            String p = indent;
            indent = indent + "  ";
            if (node.right != nullNode)
            {
                print(node.right);
            }
            String c;
            if (node.color == Color.black)
            {
                c = "(B)";
            }
            else
            {
                c = "(R)";
            }
            System.out.println(p + node.value + c);
            if (node.left != nullNode)
            {
                print(node.left);
            }
            indent = p;
        }
    }
}

cHVibGljIGNsYXNzIE1haW4KewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykKICAgIHsKICAgICAgICBqYXZhLnV0aWwuUmFuZG9tIHIgPSBuZXcgamF2YS51dGlsLlJhbmRvbSgpOwogICAgICAgIFRyZWUgdHJlZSA9IG5ldyBUcmVlKCk7CiAgICAgICAgaW50W10gYSA9IHNlcSgyNTYpOwogICAgICAgIHNmbChhLCByKTsKICAgICAgICBmb3IgKGludCBpIDogYSkKICAgICAgICB7CiAgICAgICAgICAgIHRyZWUuYWRkKGkpOwogICAgICAgIH0KICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGEubGVuZ3RoIC0gMTU7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIHRyZWUucmVtb3ZlKGFbaV0pOwogICAgICAgIH0KICAgICAgICB0cmVlLnByaW50KCk7CiAgICB9CiAgICAKICAgIHN0YXRpYyBpbnRbXSBybmQoaW50IGMsIGphdmEudXRpbC5SYW5kb20gcikKICAgIHsKICAgICAgICBpbnRbXSBhID0gbmV3IGludFtjXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGM7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGFbaV0gPSByLm5leHRJbnQoYyk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBhOwogICAgfQogICAgCiAgICBzdGF0aWMgaW50W10gc2VxKGludCBjKQogICAgewogICAgICAgIGludFtdIGEgPSBuZXcgaW50W2NdOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYzsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgYVtpXSA9IGk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBhOwogICAgfQogICAgCiAgICBzdGF0aWMgdm9pZCByZXYoaW50IGFbXSkKICAgIHsKICAgICAgICBpbnQgaSA9IDA7CiAgICAgICAgaW50IGogPSBhLmxlbmd0aCAtIDE7CiAgICAgICAgd2hpbGUgKGkgPCBqKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHQgPSBhW2ldOwogICAgICAgICAgICBhW2ldID0gYVtqXTsKICAgICAgICAgICAgYVtqXSA9IHQ7CiAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgai0tOwogICAgICAgIH0KICAgIH0KICAgIAogICAgc3RhdGljIHZvaWQgc2ZsKGludCBhW10sIGphdmEudXRpbC5SYW5kb20gcikKICAgIHsKICAgICAgICBmb3IgKGludCBpID0gYS5sZW5ndGg7IDAgPCBpOyBpLS0pCiAgICAgICAgewogICAgICAgICAgICBpbnQgaiA9IHIubmV4dEludChpKTsKICAgICAgICAgICAgaW50IHQgPSBhW2pdOwogICAgICAgICAgICBhW2pdID0gYVtpIC0gMV07CiAgICAgICAgICAgIGFbaSAtIDFdID0gdDsKICAgICAgICB9CiAgICB9Cn0KCmNsYXNzIFRyZWUKewogICAgTm9kZSByb290OwogICAgTm9kZSBudWxsTm9kZTsKICAgIAogICAgcHVibGljIFRyZWUoKQogICAgewogICAgICAgIG51bGxOb2RlID0gbmV3IE5vZGUoMCwgbnVsbCwgbnVsbCwgQ29sb3IuYmxhY2spOwogICAgICAgIHJvb3QgPSBudWxsTm9kZTsKICAgIH0KICAgIAogICAgcHVibGljIHZvaWQgYWRkKGludCB2YWx1ZSkKICAgIHsKICAgICAgICBOb2RlIG5vZGUgPSBuZXcgTm9kZSh2YWx1ZSwgbnVsbE5vZGUsIG51bGxOb2RlLCBDb2xvci5yZWQpOwogICAgICAgIEFkZGVyIGFkZGVyID0gbmV3IEFkZGVyKG5vZGUpOwogICAgICAgIGFkZGVyLmFkZCgpOwogICAgfQogICAgCiAgICBwdWJsaWMgdm9pZCByZW1vdmUoaW50IHZhbHVlKQogICAgewogICAgICAgIFJlbW92ZXIgcmVtb3ZlciA9IG5ldyBSZW1vdmVyKHZhbHVlKTsKICAgICAgICByZW1vdmVyLnJlbW92ZSgpOwogICAgfQogICAgCiAgICBwdWJsaWMgdm9pZCBwcmludCgpCiAgICB7CiAgICAgICAgUHJpbnRlciBwcmludGVyID0gbmV3IFByaW50ZXIoKTsKICAgICAgICBwcmludGVyLnByaW50KCk7CiAgICB9CiAgICAKICAgIGVudW0gQ29sb3IKICAgIHsKICAgICAgICByZWQsCiAgICAgICAgYmxhY2sKICAgIH0KCiAgICBjbGFzcyBOb2RlCiAgICB7CiAgICAgICAgaW50IHZhbHVlOwogICAgICAgIE5vZGUgbGVmdDsKICAgICAgICBOb2RlIHJpZ2h0OwogICAgICAgIENvbG9yIGNvbG9yOwogICAgICAgIAogICAgICAgIE5vZGUoaW50IHZhbHVlLCBOb2RlIGxlZnQsIE5vZGUgcmlnaHQsIENvbG9yIGNvbG9yKQogICAgICAgIHsKICAgICAgICAgICAgdGhpcy52YWx1ZSA9IHZhbHVlOwogICAgICAgICAgICB0aGlzLmxlZnQgPSBsZWZ0OwogICAgICAgICAgICB0aGlzLnJpZ2h0ID0gcmlnaHQ7CiAgICAgICAgICAgIHRoaXMuY29sb3IgPSBjb2xvcjsKICAgICAgICB9CiAgICB9CgogICAgY2xhc3MgUmVtb3ZlcgogICAgewogICAgICAgIGludCByZW1vdmVWYWx1ZTsKICAgICAgICBOb2RlIHJlc05vZGU7CiAgICAgICAgaW50IG1pblZhbHVlOwogICAgICAgIGJvb2xlYW4gYmFsYW5jZWQ7CiAgICAgICAgYm9vbGVhbiByZW1vdmVkOwogICAgICAgIAogICAgICAgIFJlbW92ZXIoaW50IHJlbW92ZVZhbHVlKQogICAgICAgIHsKICAgICAgICAgICAgdGhpcy5yZW1vdmVWYWx1ZSA9IHJlbW92ZVZhbHVlOwogICAgICAgICAgICB0aGlzLnJlc05vZGUgPSBudWxsTm9kZTsKICAgICAgICAgICAgdGhpcy5iYWxhbmNlZCA9IGZhbHNlOwogICAgICAgICAgICB0aGlzLnJlbW92ZWQgPSBmYWxzZTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgdm9pZCByZW1vdmUoKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHJvb3QgPT0gbnVsbE5vZGUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJlbW92ZShyb290KTsKICAgICAgICAgICAgICAgIGlmIChyZW1vdmVkKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJvb3QgPSByZXNOb2RlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHZvaWQgcmVtb3ZlKE5vZGUgbm9kZSkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChyZW1vdmVWYWx1ZSA8IG5vZGUudmFsdWUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChub2RlLmxlZnQgPT0gbnVsbE5vZGUpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcmVtb3ZlZCA9IGZhbHNlOwogICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZW1vdmUobm9kZS5sZWZ0KTsKICAgICAgICAgICAgICAgICAgICBpZiAocmVtb3ZlZCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIG5vZGUubGVmdCA9IHJlc05vZGU7CiAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VMKG5vZGUpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChub2RlLnZhbHVlIDwgcmVtb3ZlVmFsdWUpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKG5vZGUucmlnaHQgPT0gbnVsbE5vZGUpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICByZW1vdmVkID0gZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgcmVtb3ZlKG5vZGUucmlnaHQpOwogICAgICAgICAgICAgICAgICAgICAgICBpZiAocmVtb3ZlZCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgbm9kZS5yaWdodCA9IHJlc05vZGU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlUihub2RlKTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZW1vdmVkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICBpZiAobm9kZS5sZWZ0ID09IG51bGxOb2RlKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKG5vZGUucmlnaHQgPT0gbnVsbE5vZGUpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSBudWxsTm9kZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gbm9kZS5jb2xvciA9PSBDb2xvci5yZWQ7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gbm9kZS5yaWdodDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAobm9kZS5yaWdodCA9PSBudWxsTm9kZSkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IG5vZGUubGVmdDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlbW92ZU1pbihub2RlLnJpZ2h0KTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5vZGUucmlnaHQgPSByZXNOb2RlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgbm9kZS52YWx1ZSA9IG1pblZhbHVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZVIobm9kZSk7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgdm9pZCByZW1vdmVNaW4oTm9kZSBub2RlKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKG5vZGUubGVmdCA9PSBudWxsTm9kZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbWluVmFsdWUgPSBub2RlLnZhbHVlOwogICAgICAgICAgICAgICAgcmVzTm9kZSA9IG5vZGUucmlnaHQ7CiAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IG5vZGUuY29sb3IgPT0gQ29sb3IucmVkOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcmVtb3ZlTWluKG5vZGUubGVmdCk7CiAgICAgICAgICAgICAgICBub2RlLmxlZnQgPSByZXNOb2RlOwogICAgICAgICAgICAgICAgYmFsYW5jZUwobm9kZSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgdm9pZCBiYWxhbmNlUihOb2RlIGEpCiAgICAgICAgewogICAgICAgICAgICBpZiAoYmFsYW5jZWQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJlc05vZGUgPSBhOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgTm9kZSBiID0gYS5sZWZ0OwogICAgICAgICAgICAgICAgTm9kZSBjID0gYi5yaWdodDsKICAgICAgICAgICAgICAgIE5vZGUgZCA9IGIubGVmdDsKICAgICAgICAgICAgICAgIGlmIChhLmNvbG9yID09IENvbG9yLmJsYWNrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmIChiLmNvbG9yID09IENvbG9yLnJlZCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIE5vZGUgZSA9IGMucmlnaHQ7CiAgICAgICAgICAgICAgICAgICAgICAgIE5vZGUgZiA9IGMubGVmdDsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGUuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gcm90YXRlUjMoYSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoZi5jb2xvciA9PSBDb2xvci5yZWQpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IHJvdGF0ZVIyKGEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGYuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IHJvdGF0ZVIxKGEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGIuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjLmNvbG9yID0gQ29sb3IucmVkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAoYy5jb2xvciA9PSBDb2xvci5yZWQpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSByb3RhdGVSMihhKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGMuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChkLmNvbG9yID09IENvbG9yLnJlZCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gcm90YXRlUjEoYSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZC5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gYTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBiLmNvbG9yID0gQ29sb3IucmVkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmIChjLmNvbG9yID09IENvbG9yLnJlZCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSByb3RhdGVSMihhKTsKICAgICAgICAgICAgICAgICAgICAgICAgYS5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChkLmNvbG9yID09IENvbG9yLnJlZCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IHJvdGF0ZVIxKGEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYS5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYi5jb2xvciA9IENvbG9yLnJlZDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGQuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSBhOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYS5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYi5jb2xvciA9IENvbG9yLnJlZDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgTm9kZSByb3RhdGVSMShOb2RlIGEpCiAgICAgICAgewogICAgICAgICAgICBOb2RlIGIgPSBhLmxlZnQ7CiAgICAgICAgICAgIGEubGVmdCA9IGIucmlnaHQ7CiAgICAgICAgICAgIGIucmlnaHQgPSBhOwogICAgICAgICAgICByZXR1cm4gYjsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgTm9kZSByb3RhdGVSMihOb2RlIGEpCiAgICAgICAgewogICAgICAgICAgICBOb2RlIGIgPSBhLmxlZnQ7CiAgICAgICAgICAgIE5vZGUgYyA9IGIucmlnaHQ7CiAgICAgICAgICAgIGIucmlnaHQgPSBjLmxlZnQ7CiAgICAgICAgICAgIGEubGVmdCA9IGMucmlnaHQ7CiAgICAgICAgICAgIGMubGVmdCA9IGI7CiAgICAgICAgICAgIGMucmlnaHQgPSBhOwogICAgICAgICAgICByZXR1cm4gYzsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgTm9kZSByb3RhdGVSMyhOb2RlIGEpCiAgICAgICAgewogICAgICAgICAgICBOb2RlIGIgPSBhLmxlZnQ7CiAgICAgICAgICAgIE5vZGUgYyA9IGIucmlnaHQ7CiAgICAgICAgICAgIE5vZGUgZSA9IGMucmlnaHQ7CiAgICAgICAgICAgIGMucmlnaHQgPSBlLmxlZnQ7CiAgICAgICAgICAgIGEubGVmdCA9IGUucmlnaHQ7CiAgICAgICAgICAgIGUubGVmdCA9IGI7CiAgICAgICAgICAgIGUucmlnaHQgPSBhOwogICAgICAgICAgICByZXR1cm4gZTsKICAgICAgICB9CgogICAgICAgIHZvaWQgYmFsYW5jZUwoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGJhbGFuY2VkKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZXNOb2RlID0gYTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIE5vZGUgYiA9IGEucmlnaHQ7CiAgICAgICAgICAgICAgICBOb2RlIGMgPSBiLmxlZnQ7CiAgICAgICAgICAgICAgICBOb2RlIGQgPSBiLnJpZ2h0OwogICAgICAgICAgICAgICAgaWYgKGEuY29sb3IgPT0gQ29sb3IuYmxhY2spCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKGIuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgTm9kZSBlID0gYy5sZWZ0OwogICAgICAgICAgICAgICAgICAgICAgICBOb2RlIGYgPSBjLnJpZ2h0OwogICAgICAgICAgICAgICAgICAgICAgICBpZiAoZS5jb2xvciA9PSBDb2xvci5yZWQpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSByb3RhdGVMMyhhKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGUuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChmLmNvbG9yID09IENvbG9yLnJlZCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gcm90YXRlTDIoYSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZi5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gcm90YXRlTDEoYSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYi5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGMuY29sb3IgPSBDb2xvci5yZWQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChjLmNvbG9yID09IENvbG9yLnJlZCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IHJvdGF0ZUwyKGEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYy5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGQuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSByb3RhdGVMMShhKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSBhOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGIuY29sb3IgPSBDb2xvci5yZWQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKGMuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IHJvdGF0ZUwyKGEpOwogICAgICAgICAgICAgICAgICAgICAgICBhLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGQuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gcm90YXRlTDEoYSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiLmNvbG9yID0gQ29sb3IucmVkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgZC5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IGE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiLmNvbG9yID0gQ29sb3IucmVkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIE5vZGUgcm90YXRlTDEoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgTm9kZSBiID0gYS5yaWdodDsKICAgICAgICAgICAgYS5yaWdodCA9IGIubGVmdDsKICAgICAgICAgICAgYi5sZWZ0ID0gYTsKICAgICAgICAgICAgcmV0dXJuIGI7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIE5vZGUgcm90YXRlTDIoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgTm9kZSBiID0gYS5yaWdodDsKICAgICAgICAgICAgTm9kZSBjID0gYi5sZWZ0OwogICAgICAgICAgICBiLmxlZnQgPSBjLnJpZ2h0OwogICAgICAgICAgICBjLnJpZ2h0ID0gYjsKICAgICAgICAgICAgYS5yaWdodCA9IGMubGVmdDsKICAgICAgICAgICAgYy5sZWZ0ID0gYTsKICAgICAgICAgICAgcmV0dXJuIGM7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIE5vZGUgcm90YXRlTDMoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgTm9kZSBiID0gYS5yaWdodDsKICAgICAgICAgICAgTm9kZSBjID0gYi5sZWZ0OwogICAgICAgICAgICBOb2RlIGUgPSBjLmxlZnQ7CiAgICAgICAgICAgIGMubGVmdCA9IGUucmlnaHQ7CiAgICAgICAgICAgIGUucmlnaHQgPSBiOwogICAgICAgICAgICBhLnJpZ2h0ID0gZS5sZWZ0OwogICAgICAgICAgICBlLmxlZnQgPSBhOwogICAgICAgICAgICByZXR1cm4gZTsKICAgICAgICB9ICAgICAgICAKICAgIH0KICAgIAogICAgY2xhc3MgQWRkZXIKICAgIHsKICAgICAgICBOb2RlIGFkZE5vZGU7CiAgICAgICAgTm9kZSByZXNOb2RlOwogICAgICAgIGJvb2xlYW4gYmFsYW5jZWQ7CiAgICAgICAgYm9vbGVhbiBhZGRlZDsKCiAgICAgICAgQWRkZXIoTm9kZSBhZGROb2RlKQogICAgICAgIHsKICAgICAgICAgICAgdGhpcy5hZGROb2RlID0gYWRkTm9kZTsKICAgICAgICAgICAgdGhpcy5yZXNOb2RlID0gbnVsbE5vZGU7CiAgICAgICAgICAgIHRoaXMuYmFsYW5jZWQgPSBmYWxzZTsKICAgICAgICAgICAgdGhpcy5hZGRlZCA9IGZhbHNlOwogICAgICAgIH0KICAgICAgICAKICAgICAgICB2b2lkIGFkZCgpCiAgICAgICAgewogICAgICAgICAgICBpZiAocm9vdCA9PSBudWxsTm9kZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcm9vdCA9IGFkZE5vZGU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBhZGQocm9vdCk7CiAgICAgICAgICAgICAgICBpZiAoYWRkZWQpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcm9vdCA9IHJlc05vZGU7CiAgICAgICAgICAgICAgICAgICAgcm9vdC5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIE5vZGUgcm90YXRlUjEoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgTm9kZSBiID0gYS5sZWZ0OwogICAgICAgICAgICBhLmxlZnQgPSBiLnJpZ2h0OwogICAgICAgICAgICBiLnJpZ2h0ID0gYTsKICAgICAgICAgICAgcmV0dXJuIGI7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIE5vZGUgcm90YXRlUjIoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgTm9kZSBiID0gYS5sZWZ0OwogICAgICAgICAgICBOb2RlIGUgPSBiLnJpZ2h0OwogICAgICAgICAgICBhLmxlZnQgPSBlLnJpZ2h0OwogICAgICAgICAgICBiLnJpZ2h0ID0gZS5sZWZ0OwogICAgICAgICAgICBlLnJpZ2h0ID0gYTsKICAgICAgICAgICAgZS5sZWZ0ID0gYjsKICAgICAgICAgICAgcmV0dXJuIGU7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIE5vZGUgcm90YXRlTDEoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgTm9kZSBiID0gYS5yaWdodDsKICAgICAgICAgICAgYS5yaWdodCA9IGIubGVmdDsKICAgICAgICAgICAgYi5sZWZ0ID0gYTsKICAgICAgICAgICAgcmV0dXJuIGI7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIE5vZGUgcm90YXRlTDIoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgTm9kZSBiID0gYS5yaWdodDsKICAgICAgICAgICAgTm9kZSBlID0gYi5sZWZ0OwogICAgICAgICAgICBhLnJpZ2h0ID0gZS5sZWZ0OwogICAgICAgICAgICBiLmxlZnQgPSBlLnJpZ2h0OwogICAgICAgICAgICBlLmxlZnQgPSBhOwogICAgICAgICAgICBlLnJpZ2h0ID0gYjsKICAgICAgICAgICAgcmV0dXJuIGU7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHZvaWQgYmFsYW5jZUwoTm9kZSBhKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGJhbGFuY2VkKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZXNOb2RlID0gYTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChhLmNvbG9yID09IENvbG9yLmJsYWNrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIE5vZGUgYiA9IGEubGVmdDsKICAgICAgICAgICAgICAgICAgICBOb2RlIGMgPSBhLnJpZ2h0OwogICAgICAgICAgICAgICAgICAgIE5vZGUgZCA9IGIubGVmdDsKICAgICAgICAgICAgICAgICAgICBOb2RlIGUgPSBiLnJpZ2h0OwogICAgICAgICAgICAgICAgICAgIGlmIChjLmNvbG9yID09IENvbG9yLmJsYWNrKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGUuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gcm90YXRlUjIoYSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhLmNvbG9yID0gQ29sb3IucmVkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgZS5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGQuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSByb3RhdGVSMShhKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhLmNvbG9yID0gQ29sb3IucmVkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGIuY29sb3IgPSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IGE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChlLmNvbG9yID09IENvbG9yLnJlZCB8fCBkLmNvbG9yID09IENvbG9yLnJlZCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IGE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhLmNvbG9yID0gQ29sb3IucmVkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYi5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYy5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IGE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IGE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgdm9pZCBiYWxhbmNlUihOb2RlIGEpCiAgICAgICAgewogICAgICAgICAgICBpZiAoYmFsYW5jZWQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJlc05vZGUgPSBhOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKGEuY29sb3IgPT0gQ29sb3IuYmxhY2spCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgTm9kZSBiID0gYS5yaWdodDsKICAgICAgICAgICAgICAgICAgICBOb2RlIGMgPSBhLmxlZnQ7CiAgICAgICAgICAgICAgICAgICAgTm9kZSBkID0gYi5yaWdodDsKICAgICAgICAgICAgICAgICAgICBOb2RlIGUgPSBiLmxlZnQ7CiAgICAgICAgICAgICAgICAgICAgaWYgKGMuY29sb3IgPT0gQ29sb3IuYmxhY2spCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAoZS5jb2xvciA9PSBDb2xvci5yZWQpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc05vZGUgPSByb3RhdGVMMihhKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGEuY29sb3IgPSBDb2xvci5yZWQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoZC5jb2xvciA9PSBDb2xvci5yZWQpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IHJvdGF0ZUwxKGEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGEuY29sb3IgPSBDb2xvci5yZWQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYi5jb2xvciA9IENvbG9yLmJsYWNrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gYTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGUuY29sb3IgPT0gQ29sb3IucmVkIHx8IGQuY29sb3IgPT0gQ29sb3IucmVkKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gYTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGEuY29sb3IgPSBDb2xvci5yZWQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBjLmNvbG9yID0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gYTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gYTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfSAgICAgICAgCiAgICAgICAgfQogICAgICAgIAogICAgICAgIHZvaWQgYWRkKE5vZGUgbm9kZSkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChhZGROb2RlLnZhbHVlIDwgbm9kZS52YWx1ZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKG5vZGUubGVmdCA9PSBudWxsTm9kZSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBub2RlLmxlZnQgPSBhZGROb2RlOwogICAgICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gbm9kZS5jb2xvciA9PSBDb2xvci5ibGFjazsKICAgICAgICAgICAgICAgICAgICByZXNOb2RlID0gbm9kZTsKICAgICAgICAgICAgICAgICAgICBhZGRlZCA9IHRydWU7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgYWRkKG5vZGUubGVmdCk7CiAgICAgICAgICAgICAgICAgICAgaWYgKGFkZGVkKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbm9kZS5sZWZ0ID0gcmVzTm9kZTsKICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZUwobm9kZSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYgKG5vZGUudmFsdWUgPCBhZGROb2RlLnZhbHVlKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAobm9kZS5yaWdodCA9PSBudWxsTm9kZSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBub2RlLnJpZ2h0ID0gYWRkTm9kZTsKICAgICAgICAgICAgICAgICAgICBiYWxhbmNlZCA9IG5vZGUuY29sb3IgPT0gQ29sb3IuYmxhY2s7CiAgICAgICAgICAgICAgICAgICAgcmVzTm9kZSA9IG5vZGU7CiAgICAgICAgICAgICAgICAgICAgYWRkZWQgPSB0cnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGFkZChub2RlLnJpZ2h0KTsKICAgICAgICAgICAgICAgICAgICBpZiAoYWRkZWQpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBub2RlLnJpZ2h0ID0gcmVzTm9kZTsKICAgICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZVIobm9kZSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYWRkZWQgPSBmYWxzZTsKICAgICAgICAgICAgICAgIGJhbGFuY2VkID0gdHJ1ZTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIAogICAgY2xhc3MgUHJpbnRlcgogICAgewogICAgICAgIFN0cmluZyBpbmRlbnQ7CiAgICAgICAgCiAgICAgICAgUHJpbnRlcigpCiAgICAgICAgewogICAgICAgICAgICBpbmRlbnQgPSAiIjsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgdm9pZCBwcmludCgpCiAgICAgICAgewogICAgICAgICAgICBpZiAocm9vdCA9PSBudWxsTm9kZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJlbXB0eSIpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW5kZW50ID0gIiI7CiAgICAgICAgICAgICAgICBwcmludChyb290KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICB2b2lkIHByaW50KE5vZGUgbm9kZSkKICAgICAgICB7CiAgICAgICAgICAgIFN0cmluZyBwID0gaW5kZW50OwogICAgICAgICAgICBpbmRlbnQgPSBpbmRlbnQgKyAiICAiOwogICAgICAgICAgICBpZiAobm9kZS5yaWdodCAhPSBudWxsTm9kZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcHJpbnQobm9kZS5yaWdodCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgU3RyaW5nIGM7CiAgICAgICAgICAgIGlmIChub2RlLmNvbG9yID09IENvbG9yLmJsYWNrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjID0gIihCKSI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjID0gIihSKSI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHAgKyBub2RlLnZhbHVlICsgYyk7CiAgICAgICAgICAgIGlmIChub2RlLmxlZnQgIT0gbnVsbE5vZGUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHByaW50KG5vZGUubGVmdCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaW5kZW50ID0gcDsKICAgICAgICB9CiAgICB9Cn0K

Success #stdin #stdout 0.03s 245632KB

stdin

copy

Standard input is empty

stdout

copy

      253(B)
    251(B)
        235(R)
      233(B)
  214(R)
      192(B)
    182(B)
      165(B)
156(B)
      140(B)
    132(R)
      122(B)
  77(B)
      68(R)
    67(B)

https://ideone.com/dYfix7

language:

Java (HotSpot 12)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language