object Scanner {
  private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0
  @inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
  @inline private def hasNextByte(): Boolean =
    if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else { true }
  @inline private def hasNext(): Boolean = {
    while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
    hasNextByte()
  }
  @inline private def readByte(): Byte =
    if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else { -1 }
  def next(): String = {
    if(!hasNext()) ???
    val sb = new StringBuilder; var b = readByte()
    while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
    sb.toString
  }
  def nextInt(): Int = {
    val n = nextLong()
    if (n < Int.MinValue || Int.MaxValue < n) ???
    n.toInt
  }
  def nextLong(): Long = {
    if(!hasNext()) ???
    var minus = false; var b = readByte()
    if (b == '-') { minus = true; b = readByte() }
    def go (b: Byte, n: Long = 0): Long =
      if ('0' <= b && b <= '9') { go(readByte(), n * 10 + b - '0') }
      else if (minus) { -n } else { n }
    go(b)
  }
  def nextDouble(): Double = next.toDouble
}


object Main extends App {
  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 = -1
  val pw = new java.io.PrintWriter(System.out)
  sortedpy.map(pyi=>{
    if (pyi._1(0)!=pnow){
      sequence = 1
      pnow = pyi._1(0)
    } else {
      sequence = sequence + 1
    }
    (pyi._1(0),sequence,pyi._2)
  }).sortWith((x,y)=>{
    x._3 < y._3
  }).foreach(pyi => {
    if (pyi._1<100000){
      pw.print(0)
    }
    if (pyi._1<10000){
      pw.print(0)
    }
    if (pyi._1<1000){
      pw.print(0)
    }
    if (pyi._1<100){
      pw.print(0)
    }
    if (pyi._1<10){
      pw.print(0)
    }
    pw.print(pyi._1)
    if (pyi._2<100000){
      pw.print(0)
    }
    if (pyi._2<10000){
      pw.print(0)
    }
    if (pyi._2<1000){
      pw.print(0)
    }
    if (pyi._2<100){
      pw.print(0)
    }
    if (pyi._2<10){
      pw.print(0)
    }
    pw.print(pyi._2)
    pw.println()
  })
  pw.flush()
}