abstract class List {

  // any List, of any subclass, can tell us its length
  // However, the code must wait, since Lists can be either
  // an instance of Cons or Null.
  //
  abstract public int length();

  /* toString
   * Return the string representing the list.
   */
  abstract public String toString();
  
  /* toStringWoParens
   * Return the string representing the list, but w/o parens.
   * Intended as a helper for toString.
   */
  abstract public String toStringWoParens();

  
  /* numsDown( n )
   * Return a list with elements n..1 in that order.
   */
  static public List numsDown( int n ) {
    if (n == 0)
      return new Null();
    else
      return new Cons( n, numsDown( n-1 ) );
    }

  
  /* List.main
   * a test suite
   */
  public static void main( String[] args ) {
    List l1, l2, l3;
    l1 = new Null();
    l2 = new Cons( 3, new Cons( 5, new Cons( 4, new Null() )));
    l3 = l2;
    l3 = new Cons( 17, ((Cons) l3).cdr );

    System.out.println( "l1 is " + l1 + ", and has length " + l1.length() + "." );
    System.out.println( "l2 is " + l2 + ", and has length " + l2.length()  + ".");
    System.out.println( "l3 is " + l3 + ", and has length " + l3.length()  + ".");
    }
  }


class Null extends List {

  public int length() {
    // --- you complete this function! ---
    return -99;
    }

  public String toString() {
    return "()";
    }

  public String toStringWoParens() {
    return "";
    }

  }






class Cons extends List {
  public int car;
  public List cdr;

  public Cons( int datum, List rest ) {    // The constructor for a Cons object
    car = datum;                           //   (this is what "new" calls).
    cdr = rest;
    }

  public int length() {
    // --- you complete this function! ---
    return -99;
    }

  public String toString() {
    return "(" + toStringWoParens() + ")";
    }

  public String toStringWoParens() {
    return " " + car + cdr.toStringWoParens();
    }

  }