import scala.collection.mutable

object Main extends App {
  val Array(n, m) = io.StdIn.readLine().split(" ").map(_.toInt)
  var seq = Seq[(Int, Int)]()
  val map = mutable.LinkedHashMap[(Int, Int), String]()
  for (_ <- 0.to(n)) {
    val Array(x, y) = io.StdIn.readLine().split(" ").map(_.toInt)
    val key = (x, y)
    seq ++= Seq(key)
    map.put(key, "")
  }
  val sorted = seq.sorted.groupBy(k => k._1)
  for (e1 <- sorted) {
    for (e2 <- e1._2.zipWithIndex) {
      map.put(e2._1, "%06d%06d".format(e2._1._1, e2._2 + 1))
    }
  }
  seq.foreach(k => println(map.getOrElse(k, "?")))
}