function Main(input) {
	input = input.split("\n");
	tmp = input[0].split(" ");
	var n = parseInt(tmp[0], 10);
	var m = parseInt(tmp[0], 10);

    var id = {}
  	for(var i = 0; i <= m; i++) {
      py = input[i+1].split(" ");
      var p = py[0];
      var y = py[1];

      if (!(p in id)) {
        id[p] = {};
      }
      id[p][y] = 0;
	}
    Object.keys(id).forEach(function (key) {
        var i = 1;
        Object.keys(id[key]).forEach(function (key2) {
            id[key][key2] = i;
            i++;
        });
    });
    for(var i = 0; i <= m; i++) {
      py = input[i+1].split(" ");
      var p = py[0];
      var y = py[1];
      console.log(('000000'+p).slice(-6)+('000000'+id[p][y]).slice(-6));
	}
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));