
object Main extends App {

  import scala.io.StdIn._


  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val prefNum = Array.tabulate(n){it ⇒ 1000000000000L + (it + 1) * 1000000L}
  val id = Array.tabulate(m){_ ⇒ ""}
  val towns = Array.tabulate(m){_ ⇒
    val Array(p, y) = readLine.trim.split(' ').map(_.toInt)
    Town(p, y)
  }.zipWithIndex.sortBy(_._1.year)
  for ((town, i) ← towns){
    prefNum(town.pref - 1) += 1
    id(i) = prefNum(town.pref - 1).toString.takeRight(12)
  }
  for (i ← id){
    println(i)
  }
  case class Town(pref: Int, year: Int)
}
