import java.util.Scanner

object Main extends App {
  val scanner = new Scanner(System.in)
  val n = scanner.nextInt()
  val m = scanner.nextInt()
  val py = Array.fill(m,2)(scanner.nextInt())
  val sortedpy = py.zipWithIndex.sortWith((x,y)=>{
    if (x._1(0) == y._1(0)){
      x._1(1) < y._1(1)
    } else {
      x._1(0) < y._1(0)
    }
  })
  var sequence = 0
  var pnow = sortedpy(0)._1(0)
  sortedpy.map(pyi=>{
    if (pyi._1(0)!=pnow){
      sequence = 1
    } else {
      sequence = sequence + 1
    }
    (pyi._1(0),sequence,pyi._2)
  }).sortWith((x,y)=>{
    x._3 < y._3
  }).foreach(pyi => {
    printf("%06d%06d",pyi._1,pyi._2)
    println()
  })
}