function main(input){
  var str = input.split('\n');
  var total = [];
  for(let i=0;i<str.length;i++){
    var str2 = str[i].split(' ');
    var int = [parseInt(str2[0]),parseInt(str2[1])]
    total.push(int);
  }
  var N = total[0][0];//県の数
  var M = total[0][1];//N個の件に存在する市の総数
  var prelist = total.slice(1);
  var list = [];
  for(let j=1;j<=N;j++){
    list.push(prelist.filter(function(value,index,array){
      return array[index][0] === j;
    }))
  }
  for(let k=0;k<N;k++){
    var sum = 1;
    var pushlist = list[k].sort(function(x,y){return x[1]-y[1];});
    for(let l=0;l<pushlist.length;l++){
      var check = prelist.indexOf(pushlist[l]);
      if(check >= 0){
        prelist[check][1] = sum;
        sum += 1;
      }
    }
  }
  var prefuclist = [];
  var yearlist = []
  for(let n=0;n<M;n++){
    var prefuc = prelist[n][0]+'';
    var add1 = '0';
    var prefuc = add1.repeat(6-prefuc.length)+prefuc;
    prefuclist.push(prefuc);
  	var year = prelist[n][1]+'';
    var add2 = '0';
    var year = add2.repeat(6-year.length)+year;
    yearlist.push(year);
    console.log(prefuclist[n]+yearlist[n]);
  }
  
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));