trait Stack[+T] {
  def isEmpty: Boolean
  def top: T
  def tail: Stack[T]
}

case object Empty extends Stack[Nothing] {
  def isEmpty: Boolean = true
  def top: Nothing = throw new NoSuchElementException()
  def tail: Nothing = throw new NoSuchElementException()
}

case class Cons[+T](hd: T, tl: Stack[T]) extends Stack[T] {
  def isEmpty: Boolean = false
  def top: T = hd
  def tail: Stack[T] = tl
  def pop[U >:T]: Cons[U] = Cons(tail.top,tail.tail)
  def push[U >: T](t: U): Stack[U] = Cons(t, this)
 override def toString = top + " " +tail.toString
}