object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val N, M = sc.nextInt()
    case class City(i: Int, year: Int)
    val prefectures = Array.fill(N+1)(new scala.collection.mutable.ArrayBuffer[City]())

    (0 until M) foreach { i =>
      val p, y = sc.nextInt()
      prefectures(p).append(City(i, y))
    }

    val format = (n: Int) => "%06d".format(n)

    println((1 to N). flatMap { p =>
      prefectures(p).sortBy(_.year).zipWithIndex.map { case (city, rank) =>
        city.i -> s"${format(p)}${format(rank + 1)}"
      }
    }. sortBy(_._1). map (_._2). mkString("\n"))

  }

}
