import Main.Rational.Rational

import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._

object Main extends App {

  implicit object ConvertRationalL extends ConvertRational[Long] {
    @inline def toR(that: Long): Rational = Rational(that)
  }
  import Main.Rational._
  val push = """push (-?\d+)""".r
  val prime = primes(1 << 15)
  solve()
  def primes(upper: Int): Array[Int] = {
    val memo = Array.tabulate(upper + 1){_ ⇒ true}
    var i = 3
    for (j ← 4 to upper by 2) memo(j) = false
    while (i * i < upper){
      if (memo(i)){
        for (j ← i * 2 to upper by i){
          memo(j) = false
        }
      }
      i += 2
    }
    (2 to upper).filter(memo).toArray
  }
  @tailrec
  def solve(stack: List[List[Sqrt]] = Nil): Unit = {
    val message = readLine.trim
    message match {
      case "add" ⇒ stack match {
        case x1::x2::xs ⇒ solve(plus(x2, x1)::xs)
        case _ ⇒ ???
      }
      case "sub" ⇒ stack match {
        case x1::x2::xs ⇒ solve(minus(x2, x1)::xs)
        case _ ⇒ ???
      }
      case "mul" ⇒ stack match {
        case x1::x2::xs ⇒ solve(mul(x2, x1)::xs)
        case _ ⇒ ???
      }
      case "div" ⇒ stack match {
        case x1::x2::xs ⇒ solve(div(x2, x1)::xs)
        case _ ⇒ ???
      }
      case "sqrt" ⇒ stack match {
        case (Sqrt(1, r)::Nil)::xs ⇒ solve(List(Sqrt(r))::xs)
        case _ ⇒ ???
      }
      case "disp" ⇒ stack match {
        case Nil::xs ⇒ println(0)
          solve(xs)
        case x::xs ⇒ println(x.mkString(" + "))
          solve(xs)
        case _ ⇒ ???
      }
      case "stop" ⇒ return
      case push(n) ⇒ solve(List(Sqrt(1, Rational(n.toInt)))::stack)
      case _ ⇒ ???
    }
  }
  object Sqrt {
    def apply(rational: Rational): Sqrt = {
      if (rational.numerator == 0) new Sqrt(1, rational)
      else {
        var base = rational.numerator * rational.denominator
        var mul = 1
        var i = 0
        while (prime(i) * prime(i) <= base) {
          while (base % (prime(i) * prime(i)) == 0) {
            mul *= prime(i)
            base /= (prime(i) * prime(i))
          }
          i += 1
        }
        new Sqrt(base, Rational(mul, rational.denominator))
      }
    }

  }
  case class Sqrt (base: Long, multiple: Rational) {
    assert(base != 0)
    def *(that: Sqrt): Sqrt = {
      val g = gcd(base, that.base)
      new Sqrt(base * that.base / g / g, multiple * that.multiple * g)
    }
    def /(that: Sqrt): Sqrt = {
      val g = gcd(base, that.base)
      new Sqrt(base * that.base / g / g, g * multiple / that.multiple / that.base)
    }
    def unary_-(): Sqrt = new Sqrt(base, -multiple)

    override def toString: String = {
      if (base == 1) multiple.toString
      else if (multiple.numerator == multiple.denominator) s"sqrt($base)"
      else if (multiple.numerator == -(multiple.denominator)) s"-sqrt($base)"
      else s"${multiple}*sqrt($base)"
    }
  }
  def plus(x2: List[Sqrt], x1: List[Sqrt]): List[Sqrt] = {
    normalize(x2 ++ x1)
  }
  def minus(x2: List[Sqrt], x1: List[Sqrt]): List[Sqrt] = {
    normalize(x2 ++ x1.map(-_))
  }
  def mul(x2: List[Sqrt], x1: List[Sqrt]): List[Sqrt] = {
    normalize(x2.flatMap(s ⇒ x1.map(s * _)))
  }
  @tailrec
  def div(x2: List[Sqrt], x1:List[Sqrt]): List[Sqrt] = {
    x1 match {
      case s::Nil ⇒ normalize(x2.map(_ / s))
      case _ ⇒ x1.find(_.base != 1) match {
        case Some(s) ⇒
          val ng = x2.map(_.multiple.numerator).reduce(gcd)
          val dg = x1.map(_.multiple.denominator).reduce(gcd)
          val n = x2.map(s ⇒ new Sqrt(s.base, s.multiple / ng * dg))
          val d = x1.map(s ⇒ new Sqrt(s.base, s.multiple / ng * dg))
          val a = d.filter(_.base % s.base == 0)
          val b = d.filterNot(_.base % s.base == 0)
          val diff = minus(b, a)
          div(mul(n, diff), mul(d, diff))
        case None ⇒ ???
      }
    }
  }
  def normalize(terms: List[Sqrt]): List[Sqrt] = {
    val map = mutable.Map[Long, Rational]()
    for (term ← terms){
      if (map.contains(term.base)) {
        map(term.base) += term.multiple
      }else {
        map.put(term.base, term.multiple)
      }
    }
    map.toList.filter(_._2.numerator != 0).sortBy(_._1).map(it ⇒ new Sqrt(it._1, it._2))
  }
  object Rational {

    import scala.math._

    def apply(numerator: Long, denominator: Long): Rational = {
      val g = gcd(math.abs(denominator), math.abs(numerator))
      val signum = numerator.signum * denominator.signum
      new Rational(signum * math.abs(numerator / g), math.abs(denominator / g))
    }
    def apply(integer: Long): Rational = {
      new Rational(integer, 1)
    }
    def unapply(rational: Rational): Option[(Long, Long)] = {
      Some(rational.numerator, rational.denominator)
    }
    private def gcd(a: Long, b: Long): Long = {
      b match {
        case 0l ⇒ a
        case _ ⇒ gcd(b, a % b)
      }
    }
    class Rational(val numerator: Long, val denominator: Long) {
      def +(that: Rational): Rational = Rational(numerator * that.denominator + denominator * that.numerator, denominator * that.denominator)
      def -(that: Rational): Rational = Rational(numerator * that.denominator - denominator * that.numerator, denominator * that.denominator)
      def *(that: Rational): Rational = Rational(numerator * that.numerator, denominator * that.denominator)
      def /(that: Rational): Rational = Rational(numerator * that.denominator, denominator * that.numerator)
      def +[N](that: N)(implicit convert: ConvertRational[N]): Rational = this + convert.toR(that)
      def -[N](that: N)(implicit convert: ConvertRational[N]): Rational = this - convert.toR(that)
      def *[N](that: N)(implicit convert: ConvertRational[N]): Rational = this * convert.toR(that)
      def /[N](that: N)(implicit convert: ConvertRational[N]): Rational = this / convert.toR(that)
      def <[N](that: N)(implicit convert: ConvertRational[N]): Boolean = RationalNumeric.compare(this, convert.toR(that)) < 0
      def <=[N](that: N)(implicit convert: ConvertRational[N]): Boolean = RationalNumeric.compare(this, convert.toR(that)) <= 0
      def >[N](that: N)(implicit convert: ConvertRational[N]): Boolean = RationalNumeric.compare(this, convert.toR(that)) > 0
      def >=[N](that: N)(implicit convert: ConvertRational[N]): Boolean = RationalNumeric.compare(this, convert.toR(that)) >= 0
      def unary_-(): Rational = Rational(-numerator, denominator)
      override def equals(obj: Any): Boolean = {
        super.equals(obj)
      }
      def equals[N](that: N)(implicit convert: ConvertRational[N]): Boolean = {
        RationalNumeric.compare(this, convert.toR(that)) == 0
      }
      override def toString: String = {
        if (denominator == 1) numerator.toString
        else s"$numerator/$denominator"
      }
    }
    implicit object RationalNumeric extends Fractional[Rational] {
      override def plus(x: Rational, y: Rational): Rational = x + y
      override def minus(x: Rational, y: Rational): Rational = x - y
      override def times(x: Rational, y: Rational): Rational = x * y
      override def negate(x: Rational): Rational = -x
      override def fromInt(x: Int): Rational = Rational(x)
      override def toInt(x: Rational): Int = x.toLong.toInt
      override def toLong(x: Rational): Long = x.numerator / x.denominator
      override def toFloat(x: Rational): Float = x.toDouble().toFloat
      override def toDouble(x: Rational): Double = x.numerator.toDouble / x.denominator
      override def compare(x: Rational, y: Rational): Int = (x - y).numerator.compare(0)
      override def div(x: Rational, y: Rational): Rational = x / y
    }
  }
  implicit class ToRational[N](val value: N)(implicit convert: ConvertRational[N]) {
    def +(that: Rational): Rational = convert.toR(value) + that
    def -(that: Rational): Rational = convert.toR(value) - that
    def *(that: Rational): Rational = convert.toR(value) * that
    def /(that: Rational): Rational = convert.toR(value) / that
  }
  trait ConvertRational[N]{
    def toR(that: N): Rational
  }
  @tailrec
  def gcd(a: Long, b: Long): Long = {
    b match {
      case 0 ⇒ a
      case _ ⇒ gcd(b, a % b)
    }
  }

  implicit class Scope[T](val value: T) extends AnyVal {
    @inline def also(@inline func: T ⇒ Unit): T = {
      func(value)
      value
    }
    @inline def let[A](@inline func: T ⇒ A): A = func(value)
  }
}


Measured memory_bytes: 48708