object Main
  extends App {

  case class State[S, A](run: S => (S, A)) { self =>
    def map[B](f: A => B): State[S, B] = {
      //      State((s: S) => (s, f(self.run(s)._2)))
      flatMap(a => State.unit(f(a)))
    }

    def flatMap[B](f: A => State[S, B]): State[S, B] =
      State((s: S) => {
        val (s1, a) = self.run(s)
        f(a).run(s1)
      })
  }

  object State {
    def unit[S, A](a: A): State[S, A] = State(s => (s, a))
  }

  implicit class StreamOps[S, A](stream: Stream[State[S, A]]) {
    def sequence: State[S, Stream[A]] =
      stream.foldLeft(State.unit[S, Stream[A]](Stream.empty[A]))(
        (acc, h) => acc.flatMap(st => h.map(a => a #:: st))
      )
  }

  def f(a: Int): State[(Seq[Int], Seq[Int]), Option[Int]] =
    State { case (stack: Seq[Int], trail: Seq[Int]) =>
      if (a == 0) ((stack.tail, stack.head +: trail), Some(stack.head)) else ((a +: stack, trail), None)
    }

  //  import scala.collection.immutable.Stack
  //  Stream
  //    .continually(readLine)
  //    .takeWhile(_ != null)
  //    .map(_.toInt)
  //    .foldLeft(Stack.empty[Int]) {
  //      case (stack, h) =>
  //        if (h == 0) stack.pop2 match {
  //          case (e, tail) => println(e); tail
  //        } else stack.push(h)
  //    }

  Stream
    .continually(readLine)
    .takeWhile(_ != "")
    .map(_.toInt)
    //  val track = Seq(1, 6, 0, 8, 10, 0, 0, 0)
    .map(f)
    .sequence
    .run((Nil, Nil))
    ._1._2
    .reverse
    .foreach(println)
}
