function zero_padding_number(num){
  return ('000000' + num.toString()).slice(-6);
}

function main(input){
  const lines = input.split('\n');
  const N =parseInt(lines[0].split(' ')[0]);
  const M =parseInt(lines[0].split(' ')[1]);
  var pys = [];
  for(var i=0;i<M;i++){
    var line = lines[1+i].split(' ').map(x => parseInt(x))
    pys.push([i, line[0],line[1]]);
  }

  var p_sorted = pys.sort(function(a,b){return a[1]-b[1];})
//console.log(p_sorted)

  var p_y_sorted = [];
  for(var i=0;i<N;i++){
    var p_cities = p_sorted.filter(x => x[1]==(i+1));
    var p_sorted_cities = p_cities.sort(function(a,b){return a[2]-b[2]});

    for(var j=0;j<p_sorted_cities.length;j++){
      var id = zero_padding_number(p_sorted_cities[j][1])+zero_padding_number(j+1)
      p_sorted_cities[j].push(id);
      p_y_sorted.push(p_sorted_cities[j]);
    }
  }
  const stdin_sorted_cities = p_y_sorted.sort(function(a,b){return a[0]-b[0];})
  for(var i=0;i<M;i++){
    console.log(stdin_sorted_cities[i][3])
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));