object Main extends App {
  import scala.io.StdIn._
  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val cityCount = Array.fill(n){0}
  var result = Nil: List[(Int, String)]
  for ((Array(p, y), i) ← Array.fill(m){readLine.trim.split(' ').map(_.toInt)}.zipWithIndex.sortBy(_._1(1))) {
    cityCount(p - 1) += 1
    result ::= (i, f"$p%06d${cityCount(p - 1)}%06d")
  }
  result.sortBy(_._1).map(_._2).foreach(println)
}