
object Main extends App {

  import scala.io.StdIn._


  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val prefNum = Array.tabulate(n){_ ⇒ 0}
  val id = Array.tabulate(m){_ ⇒ 1000000000000L}
  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) + town.pref * 1000000
  }
  for (i ← id){
    println(i.toString.takeRight(12))
  }
  case class Town(pref: Int, year: Int)
}
