//> using dep org.scala-lang.modules::scala-parser-combinators::2.3.0

package aoc

import scala.util.parsing.combinator._

def iterate[T](get: => T | Null) =
  Iterator.continually(get).takeWhile(_ != null).map(_.nn)

def lines = iterate(scala.io.StdIn.readLine())

trait CommonParser extends RegexParsers:
  val num = """-?(0|[1-9]\d*)""".r ^^ { _.toInt }
  val long = """-?(0|[1-9]\d*)""".r ^^ { _.toLong }

object CommonParser extends CommonParser

extension [T](ss: Seq[T])
  @scala.annotation.tailrec
  def findMap[U](f: T => Option[U]): Option[U] =
    if ss.isEmpty then None
    else
      val (head, tail) = (ss.head, ss.tail)
      f(head) match
        case None        => tail.findMap(f)
        case v @ Some(_) => v

  def splitBy(cond: T => Boolean): Seq[Seq[T]] =
    val splitPos = ss.indexWhere(cond)
    if splitPos == -1 then Seq(ss)
    else ss.take(splitPos) +: ss.drop(splitPos + 1).splitBy(cond)