object Main{
  def main(args:Array[String]):Unit={
    var record:Map[Int,Array[Int]] = Map()
    var NM = readLine.split(" ").map(x => x.toInt)
    for(i <- 0 until NM(1)){
      var tmp = readLine.split(" ").map(x => x.toInt)
      var tmpArray = record.getOrElse(tmp(0),Array())
      tmpArray = tmpArray :+ tmp(1)
      record += (tmp(0) -> tmpArray)
    }
    var keys = record.keySet.toArray.sorted
    for(i <- 0 until keys.length){
      var res = ""
      var value = record.getOrElse(keys(i),Array())
      var len = 6-keys(i).size
      for(i <- 0 until len){
      	res += "0"
      }
      res+=keys(i).toString
      
      for(i <- 0 until value.length){
        var tmp = ""
        var valueL = 6-value(i).size
        for(j <- 0 until valueL){
          tmp+="0"
        }
        tmp+=value(i).toString
        println(res+tmp)
      }
    }
    
  }
  
  
}