// Data Definition: IntList := new Empty() + new Cons(int, IntList)

abstract class IntList {
  
  /** Returns the length of this */
  abstract int length();
  
  /** Returns the sum of the elements in this */
  abstract int sum();
  
  /** Returns the sum of the elements in this */
  abstract int getSum();
  
  /** Returns the sum of accum and the elements in this;
   *  accum is the running sum. */
  abstract int getSumHelp(int accum);
  
  /** Returns the list consisting of this followed by other, e.g.
   *  [1 2].concat([3 4]) = [1 2 3 4] */
  abstract IntList concat(IntList other);
  
  /** Returns the list containing the elements of this in reverse order */
  IntList rev() { return this.revHelp(Empty.ONLY); }
  
  /** Returns the list containing the elements of this in reverse order 
   *  concatenated onto other */
  abstract IntList revHelp(IntList other);

  /** Returns String representation of this without enclosing parens. */
  abstract String toStringHelp();   
}

class Empty extends IntList {

  static Empty ONLY = new Empty(); // singleton pattern

  /* constructor */
  private Empty() {} 
  
  int length() { return 0; }
  
  int sum() { return 0; }
  
  int getSum() { return 0; }
  int getSumHelp(int accum) { return accum; }
  
  IntList concat(IntList other) { return other; }

  IntList revHelp(IntList accum) { return accum; }

  String toStringHelp() { return ""; }
  public String toString() { return "[]"; }
}

class Cons extends IntList {

  int first;
  IntList rest;

  /* constructor */
  Cons(int f, IntList r) {
    first = f;
    rest = r;
  }

  /* accessors */
  int getFirst() { return first; }
  IntList getRest() { return rest;  }
  
  int length() { return  1 + rest.length(); }
  
  int sum() { return  first + rest.sum(); }
  
  int getSum() { return rest.getSumHelp(first); }
  int getSumHelp(int accum) { return rest.getSumHelp(accum + first); }
  
  IntList revHelp(IntList accum) { 
    return rest.revHelp(new Cons(first,accum));
  }
  
  IntList concat(IntList other) { 
    return new Cons(first, rest.concat(other)); 
  }

  public String toString() {
    return "[" + first + rest.toStringHelp() + "]";
  }
  String toStringHelp() {
    return " " + first + rest.toStringHelp();  
  }
}