gMatrix.scala

import java.io.FileReader
import scala.io.StdIn
import scala.math

object gMatrix extends App {
  def genMatrix(n: Int, c: Int, x: Int, as: Array[Int], bs: Array[Int]): IndexedSeq[IndexedSeq[Long]] = {
    for (i <- 0 until n) yield {
      for (j <- 0 until n) yield ((as(i) * (i + 1) + bs(j) * (j + 1) + c) % x).toLong
    }
  }

  def reduceKMax(row: IndexedSeq[Long], k: Int): IndexedSeq[Long] = {
    if (k == 1) row
    else {
      def reduceKMaxInternal(row: IndexedSeq[Long], prevMax: Long, prevHead: Long): List[Long] = {
        if (row.size < k) Nil
        else if (prevHead == prevMax) {
          val subMax = row.take(k).max
          subMax :: reduceKMaxInternal(row.tail, subMax, row.head)
        } else {
          val nexMax = math.max(prevMax, row(k - 1))

          nexMax :: reduceKMaxInternal(row.tail, nexMax, row.head)
        }
      }

      val subMax = row.take(k).max

      (subMax :: reduceKMaxInternal(row.tail, subMax, row.head)).toIndexedSeq
    }
  }

  def flipMatrix(matrix: IndexedSeq[IndexedSeq[Long]]) = {
    val rows = matrix.size
    val cols = matrix(0).size

    for (i <- 0 until cols) yield { for (j <- 0 until rows) yield matrix(j)(i) }
  }

  def solve(n: Int, k: Int, c: Int, x: Int, as: Array[Int], bs: Array[Int]): Long = {
    val matrix = genMatrix(n, c, x, as, bs)
    //    Console println(f"matrix=$matrix")

    val rowReducedFlipped = flipMatrix(for (i <- 0 until n) yield reduceKMax(matrix(i), k))
    //    Console println(f"rowReducedFlipped=$rowReducedFlipped")

    (for (i <- 0 until rowReducedFlipped.size) yield reduceKMax(rowReducedFlipped(i), k).sum).sum
  }

  
  //  val fileName = "sample"
  //  val fileName = "D-small-practice"
  val fileName = "D-large-practice"

  val inFile = new FileReader(fileName + ".in")
  val pstream = new java.io.PrintStream(fileName + ".out")

  val current = System.currentTimeMillis()

  try {
    val results = Console.withIn(inFile) {
      val numCase = StdIn.readLine().toInt

      for (i <- 1 to numCase) yield {
        val nkcx = StdIn.readLine().split(" ").map(_.toInt)

        val n = nkcx(0)
        val k = nkcx(1)
        val c = nkcx(2)
        val x = nkcx(3)

        val as = StdIn.readLine().split(" ").map(_.toInt)
        val bs = StdIn.readLine().split(" ").map(_.toInt)

        //        val asStr = as mkString " " 
        //        val bsStr = bs mkString " "
        //        Console println (f"solve case=#$i n=$n k=$k c=$c x=$x as=$asStr bs=$bsStr")
        solve(n, k, c, x, as, bs)
      }
    }

    Console.withOut(pstream) {
      for (i <- 1 to results.size) {
        val result = results(i - 1)
        println(f"Case #$i: $result")
      }
    }
  } finally {
    inFile.close()
    pstream.close()
  }

  val elapsed = System.currentTimeMillis() - current
  Console println (f"Elapsed Time=${elapsed}ms")
}