var toInt = x=>parseInt(x,10);
var toIntArr = arr=>arr.map(x=>toInt(x));
var abs = x=>x>0?x:-x;
function min(){var rest=arguments,v=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]<v)v=rest[i];return v}
function max(){var rest=arguments,v=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]>v)v=rest[i];return v}
function gcd(){var rest=arguments,v=rest[0],temp=(a,b)=>b?temp(b,a%b):a;for(var i=1;i<rest.length;i++)v=temp(v,rest[i]);return v}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
 
function Main(input){
	var input = input.split('\n');
	var nm = toIntArr(input[0].split(' '));
	var n = nm[0];
	var m = nm[1];

	var pys = [];
	for(var i = 0; i < m; i++){
		pys[i] = toIntArr(input[i+1].split(' '));
	}

	var ken = [];

	var py;
	for(var i = 0; i < m; i++){
		py = pys[i];
		if(ken[py[0]] === undefined){
			ken[py[0]] = [[i+1,py[1]]];
		}else{
			ken[py[0]].push([i+1,py[1]]);
		}
	}

	var anss = [];
	var strP, strX;
	var l;
	for(var i = 1; i <= n; i++){
		if(ken[i] !== undefined){
			ken[i].sort((a,b)=>a[1]-b[1]);
			l = ken[i].length;
			for(var j = 0; j < l; j++){
				strP = i.toString().padStart(6,'0');
				strX = (j+1).toString().padStart(6,'0');
				anss[ken[i][j][0]] = strP + strX;
			}
		}
	}

	for(var i = 0; i < m; i++){
		console.log(anss[i]);
	}	

}

