object Main extends App {
def createInitList(r:Range, depth:Int):Map[Int, Int] = {
  depth match {
    case x if x<0 => Map(1 -> 1)
    case 1 => r.map(v=> (v->1)).toMap
    case n => {
      val m = createInitList(r, depth-1)
      val ret = collection.mutable.Map[Int, Int]().withDefaultValue(0)
      for(k <- r; v <- m){
        ret(v._1 * k) = ret(v._1 * k) + v._2
      }
      ret.toMap
    }
  }
}
 
def medianFromCompressedSeq(lst:List[Tuple2[Int, Int]]):Int = {
  val sorted = lst.sortBy(_._1)
  println(sorted.take(20))
  val cumulativeList = sorted.foldLeft(List(Tuple3(0,0,0)))((r, v) => {
    Tuple3(v._1, r.head._3, v._2 + r.head._3)::r
  })
  val tot = cumulativeList.head._3
 
  // 本当は tot が偶数/奇数で処理が微妙にちがうが、
  // sample でも奇数決め打ちでやっているのでそれに従う
  val ind = (tot+1)/2
  val ret = cumulativeList.find(v => {v._2 < ind && v._3 >= ind})
  assert(ret != None)
  ret.get._1
}
 
val vec = createInitList(1 to 31, 5).toList
println(medianFromCompressedSeq(vec))
}

b2JqZWN0IE1haW4gZXh0ZW5kcyBBcHAgewpkZWYgY3JlYXRlSW5pdExpc3QocjpSYW5nZSwgZGVwdGg6SW50KTpNYXBbSW50LCBJbnRdID0gewogIGRlcHRoIG1hdGNoIHsKICAgIGNhc2UgeCBpZiB4PDAgPT4gTWFwKDEgLT4gMSkKICAgIGNhc2UgMSA9PiByLm1hcCh2PT4gKHYtPjEpKS50b01hcAogICAgY2FzZSBuID0+IHsKICAgICAgdmFsIG0gPSBjcmVhdGVJbml0TGlzdChyLCBkZXB0aC0xKQogICAgICB2YWwgcmV0ID0gY29sbGVjdGlvbi5tdXRhYmxlLk1hcFtJbnQsIEludF0oKS53aXRoRGVmYXVsdFZhbHVlKDApCiAgICAgIGZvcihrIDwtIHI7IHYgPC0gbSl7CiAgICAgICAgcmV0KHYuXzEgKiBrKSA9IHJldCh2Ll8xICogaykgKyB2Ll8yCiAgICAgIH0KICAgICAgcmV0LnRvTWFwCiAgICB9CiAgfQp9CgpkZWYgbWVkaWFuRnJvbUNvbXByZXNzZWRTZXEobHN0Okxpc3RbVHVwbGUyW0ludCwgSW50XV0pOkludCA9IHsKICB2YWwgc29ydGVkID0gbHN0LnNvcnRCeShfLl8xKQogIHByaW50bG4oc29ydGVkLnRha2UoMjApKQogIHZhbCBjdW11bGF0aXZlTGlzdCA9IHNvcnRlZC5mb2xkTGVmdChMaXN0KFR1cGxlMygwLDAsMCkpKSgociwgdikgPT4gewogICAgVHVwbGUzKHYuXzEsIHIuaGVhZC5fMywgdi5fMiArIHIuaGVhZC5fMyk6OnIKICB9KQogIHZhbCB0b3QgPSBjdW11bGF0aXZlTGlzdC5oZWFkLl8zCgogIC8vIOacrOW9k+OBryB0b3Qg44GM5YG25pWwL+Wlh+aVsOOBp+WHpueQhuOBjOW+ruWmmeOBq+OBoeOBjOOBhuOBjOOAgQogIC8vIHNhbXBsZSDjgafjgoLlpYfmlbDmsbrjgoHmiZPjgaHjgafjgoTjgaPjgabjgYTjgovjga7jgafjgZ3jgozjgavlvpPjgYYKICB2YWwgaW5kID0gKHRvdCsxKS8yCiAgdmFsIHJldCA9IGN1bXVsYXRpdmVMaXN0LmZpbmQodiA9PiB7di5fMiA8IGluZCAmJiB2Ll8zID49IGluZH0pCiAgYXNzZXJ0KHJldCAhPSBOb25lKQogIHJldC5nZXQuXzEKfQoKdmFsIHZlYyA9IGNyZWF0ZUluaXRMaXN0KDEgdG8gMzEsIDUpLnRvTGlzdApwcmludGxuKG1lZGlhbkZyb21Db21wcmVzc2VkU2VxKHZlYykpCn0=