
object Main extends App {

  import scala.io.StdIn._

  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val pref = Array.tabulate(n){ _ ⇒ 0}
  val town = Array.tabulate(m){_ ⇒
    val Array(p, y) = readLine.trim.split(' ').map(_.toInt)
    Town(p, y)
  }.zipWithIndex.sortBy(_._1.year)

  (for ((Town(p, y), i) ← town) yield {
    pref(p - 1) += 1
    (("0" * 6 + p.toString).takeRight(6) + ("0" * 6 + pref(p - 1).toString).takeRight(6), i)
  }).sortBy(_._2).foreach(it ⇒ println(it._1))

  case class Town(pref: Int, year:Int)
  implicit class ScopeFunc[T](val value: T) {
    def let[A](func: T ⇒ A): A = func(value)
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
  }
}

/*
 */