static class PersistentArray {
        static class Node {
            Node left;
            Node right;
            int value;

            public Node(Node left, Node right, int value) {
                this.left = left;
                this.right = right;
                this.value = value;
            }

            public Node(Node left, Node right) {
                this.left = left;
                this.right = right;
            }

            public Node() {
                this(null, null, 0);
            }

            public Node(int value) {
                this.value = value;
            }

        }

        Node root;
        int n;

        public PersistentArray(int n) {
            this.n = n;
            root = new Node();
            makeArray(root, 0, n);
        }

        public PersistentArray(Node root, int n) {
            this.root = root;
            this.n = n;
        }

        static void makeArray(Node v, int left, int right) {
            int mid = (left + right) >> 1;
            if (left < mid) {
                v.left = new Node();
                makeArray(v.left, left, mid);
            }
            if (mid < right) {
                v.right = new Node();
                makeArray(v.right, mid, right);
            }
        }

        static Node set(Node v, int left, int right, int index, int newValue) {
            if (left + 1 == right) {
                return new Node(newValue);
            }
            int mid = (left + right) >> 1;
            if (index < mid) {
                return new Node(set(v.left, left, mid, index, newValue),
                        v.right);
            } else {
                return new Node(v.left, set(v.right, mid, right, index,
                        newValue));
            }
        }

        public PersistentArray set(int x, int y) {
            return new PersistentArray(set(root, 0, n, x, y), n);
        }

        public int get(int x) {
            int left = 0;
            int right = n;
            Node node = root;
            while (left + 1 < right) {
                int mid = (left + right) >> 1;
                if (x < mid) {
                    node = node.left;
                    right = mid;
                } else {
                    node = node.right;
                    left = mid;
                }
            }
            return node.value;
        }