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 listlist=(1 to N).map(i=>PY.filter(_._1 == i).sorted)
  val printlist = PY.map(i=>(listlist(i._1-1).indexOf(i)+1,i._1))
  printlist.foreach(i=>println(f"${i._2}%06d${i._1}%06d"))
}

