function main(input) {
  var N = input[0].split(" ")[0]-0;
  var M = input[0].split(" ")[1]-0;
  var list = [];
  for(var i=1;i<=M;i++){
    list.push(input[i].split(" ").map(v=>v-0));
  }
  list = list.sort((a,b)=>(a[0]-b[0])||(a[1]-b[1]));
  var map = {};
  list.forEach((v,i)=>{
    var c = v[0];
    var y = v[1];
    if(!map[c]){
      map[c] = {};
    }
    map[c][y] = Object.keys(map[c]).length+1;
  });
  for(var i=1;i<=M;i++){
    var c = input[i].split(" ")[0];
    var y = input[i].split(" ")[1];
    var num = map[c][y];
    console.log(("000000"+c).slice(-6) + ("000000"+num).slice(-6));
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"))
