function Main(input){
	input = input.split("\n");
  var NM = input[0].split(" ");
  var N = NM[0]*1;
  var M = NM[1]*1;
  var prefs = [];
  var cities = [];
  for(var i = 0;i < M;i++){
  	var a = input[i+1];
    var P = a.split(" ")[0]*1;
    var Y = a.split(" ")[1]*1;
    if(prefs[P]===undefined)prefs[P] = [];
    prefs[P].push({i:i,pref:P,year:Y});
  }
  for(var i = 0;i <= N;i++){
  	var pref = prefs[i];
    if(!pref)continue;
    pref.sort(function(a,b){
    	return a.year-b.year;
    })
    for(var j = 0;j < pref.length;j++){
    	pref[j].ID = ("00000"+pref[j].pref).slice(-6)+("00000"+(j+1)).slice(-6);
      cities.push(pref[j]);
    }
  }
  cities.sort(function(a,b){
  	return a.i-b.i;
  })
  return cities.map(a=>a.ID).join("\n");
}

console.log(Main(require("fs").readFileSync("/dev/stdin", "utf8")));