Cryptopangrams.scala

import java.io.FileInputStream

import scala.io.StdIn

object Solution extends App {
  Console.setIn(new FileInputStream("example.in"))

  def unzip(initial: BigInt, pairs: List[BigInt]): List[BigInt] = pairs match {
    case Nil => Nil
    case x :: xs =>
      val next = x / initial
      next :: unzip(next, xs)
  }

  def solve(n: BigInt, cipherText: IndexedSeq[BigInt]): String = {
    (0 until cipherText.size - 1).find(i => cipherText(i) != cipherText(i + 1)) match {
      case Some(x) =>
        val gcd = cipherText(x) gcd cipherText(x + 1)
        val (front, back) = cipherText splitAt x + 1
        val primeSeq = unzip(gcd, front.toList.reverse).reverse ::: gcd :: unzip(gcd, back.toList)

        (primeSeq map (primeSeq.distinct.sorted zip ('A' to 'Z')).toMap).mkString

      case None => throw new RuntimeException("None")
    }
  }

  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { i => {
    val Array(n, _) = StdIn.readLine().split(" ").map(BigInt(_))
    val cipherText = StdIn.readLine().split(" ").map(BigInt(_))
    val answer = solve(n, cipherText.toVector)
    println(s"Case #$i: $answer")
  }
  }
}