object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val N, M = sc.nextInt()

    val prefectures = Array.fill(N+1)(
      new scala.collection.mutable.ArrayBuffer[Int]())
    val result = new Array[String](M)
    val year = new Array[Int](M)

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

    @inline val format = (n: Long) => "%012d".format(n)

    (1 to N). foreach { p =>
      val prefecture = prefectures(p).sortBy(i => year(i))
      val l = prefecture.size
      var i = 1
      while (i <= l) {
        val city = prefecture(i-1)
        result(city) = format(p * 1000000L + i)
        i += 1
      }
    }

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

  }

}
