function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0].split(" ")[0]);
  var M = parseInt(input[0].split(" ")[1]);
  C=new Array(M);
  P=new Array(0);
  for(i=0;i<M;i++){
    tmp=input[i+1].split(" ");
    Csub=[parseInt(tmp[0]),parseInt(tmp[1])];
    C[i]=Csub;
  }
  C.sort(function(a, b) {
		if (a[0] < b[0]) return -1;
		if (a[0] > b[0]) return 1;
		if (a[1] < b[1]) return -1;
		if (a[1] > b[1]) return 1;
		return 0;
	});
  for(i=0;i<M;i++){
    var c="";
    var y="";
    if(C[i][0]<10){
      c=`00000${C[i][0]}`;
    }else if(C[i][0]<100){
      c=`0000${C[i][0]}`;
    }else if(C[i][0]<1000){
      c=`000${C[i][0]}`;
    }else if(C[i][0]<10000){
      c=`00${C[i][0]}`;
    }else if(C[i][0]<100000){
      c=`0${C[i][0]}`;
    }else{
      c=`${C[i][0]}`;
    }
    if(i==0){
      var cnt=1;
    }else if(C[i][0]!=C[i-1][0]){
      cnt=1;
    }else{
      cnt++;
    }
    if(cnt<10){
      y=`00000${cnt}`;
    }else if(cnt<100){
      y=`0000${cnt}`;
    }else if(cnt<1000){
      y=`000${cnt}`;
    }else if(cnt<10000){
      y=`00${cnt}`;
    }else if(cnt<100000){
      y=`0${cnt}`;
    }else{
      y=`${cnt}`;
    }
    P.push(`${c}${y}`);
  }
  var ans=P.join("\n");


  console.log('%s', ans);
}
  
// "実行する"ボタンを押した時に実行される関数 (デバッグ用)
function debug(){
  var input = document.getElementById("input").value;
  Main(input);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
