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]())
    val result = new Array[String](M)

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

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

    (1 to N). foreach { p =>
      val prefecture = prefectures(p)
      val l = prefecture.size
      var i = 1
      while (i <= l) {
        val city = prefecture(i-1)
        result(city.i) = s"${format(p)}${format(i)}"
        i += 1
      }
    }

    println(result.mkString("\n"))

  }

}
