object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    import scala.collection.mutable.PriorityQueue

    val N, M = sc.nextInt()
    case class City(i: Int, p: Int, year: Int)
    val prefectures: Array[PriorityQueue[City]] =
      Array.fill(N+1)(PriorityQueue.empty[City](Ordering.by[City, Int](city => city.year)(Ordering.Int.reverse)))
    (1 to M) foreach { i =>
      val p, y = sc.nextInt()
      prefectures(p).enqueue(City(i, p, y))
    }

    println(prefectures. flatMap { prefecture =>
      prefecture.toSeq.zipWithIndex
    }. sortBy (_._1.i). map { city =>
      s"${"%06d".format(city._1.p)}${"%06d".format(city._2 + 1)}"
    }. mkString("\n"))
  }

}