object Main extends App{
  val sc = new java.util.Scanner(System.in)
  val N,M= sc.nextInt
  val PY = (1 to M).map(i=>(sc.nextInt,sc.nextInt))
  val list = PY.sortBy(i=>i._2).groupBy(i=>i._1)
  val printlist = PY.map(i=>(i._1,list(i._1).indexOf(i)+1))
  printlist.foreach(i=>println(f"${i._1}%06d${i._2}%06d"))
}

