import scala.util.Sorting

object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n, m = sc.nextInt
    val items = new Array[(Int, Int, Int, String)](m)
    for (i <- 0 until m) {
      items(i) = (i, sc.nextInt, sc.nextInt, "")
    }

    Sorting.quickSort(items)(Ordering.by(_._3))
    val cityCount = new Array[Int](n)
    val cityNumbers = new Array[String](m)
    for (item <- items) {
      val i = item._1
      val p = item._2 - 1
      val num = cityCount(p) + 1
      cityNumbers(i) = "%06d%06d".format(p + 1, num)

      cityCount(p) += 1
    }

    cityNumbers.foreach(println)
  }

}
