import java.util.ArrayList;

public class PersistentVector<T> {

  private static class Tree<T> {
    public T key;
    public int size;
    private Tree<T> left, right;

    private Tree(T key, int initSize, Tree<T> left, Tree<T> right) {
      this.key = key;
      this.left = left;
      this.right = right;
      size = initSize;
      if (left != null) size += left.size;
      if (right != null) size += right.size;
    }

    public Tree(T key) {
      this(key, 1, null, null);
    }

    public T get(int index) {
      if (size == 1) return key;
      if (index < left.size) return left.get(index);
      else return right.get(index - left.size);
    }

    public static <T> Tree<T> merge(Tree<T> left, Tree<T> right) { 
      return new Tree<>(null, 0, left, right);
    }
  }

  public int size;
  private long digits;
  private ArrayList<Tree<T>> roots;

  public PersistentVector() {
    size = 0;
    digits = 0;
    roots = new ArrayList<>();
  }

  private PersistentVector(PersistentVector<T> from) {
    size = from.size;
    digits = from.digits;
    roots = (ArrayList<Tree<T>>) from.roots.clone();
  }

  public PersistentVector<T> pushBack(T value) {
    Tree<T> carry = new Tree<>(value);
    PersistentVector<T> result = new PersistentVector<>(this);
    result.size += 1;
    for (int i = 0; carry != null; ++i) {
      if (i == result.roots.size()) {
        result.roots.add(carry);
        break;
      }
      if((result.digits & (1L << i)) != 0) {
        Tree<T> tmp = result.roots.get(i);
        result.roots.set(i, carry);
        carry = tmp;
      } else {
        result.roots.set(i, Tree.merge(carry, result.roots.get(i)));
        carry = null;
      }
      result.digits ^= (1L << i);
    }
    return result;
  }

  public PersistentVector<T> popBack() {
    PersistentVector<T> result = new PersistentVector<>(this);
    result.size -= 1;
    for (int i = 0; i < result.roots.size(); ++i) {
      if ((result.digits & (1L << i)) != 0) {
        result.roots.set(i, result.roots.get(i).right);
        result.digits ^= (1L << i);
        break;
      } else {
        if (i + 1 >= result.roots.size()) {
          result.roots.remove(i);
        } else {
          if ((result.digits & (1L << (i + 1))) != 0) {
            result.roots.set(i, result.roots.get(i + 1).left);
          } else {
            result.roots.set(i, result.roots.get(i + 1));
          }
          result.digits ^= (1L << i);
        }
      }
    }
    return result;
  }

  public T get(int index) {
    index = size - 1 - index;
    for (int i = 0; ;++i) {
      if (index < roots.get(i).size) return roots.get(i).get(index);
      else index -= roots.get(i).size;
    }
  }
}