function Main(input) {
	input = input.split("\n");
	var tmp = input[0].split(" ");
    var N = parseInt(tmp[0], 10);
    var M = parseInt(tmp[1], 10);
    var input2dArray = getInputIn2dArray(input,N,M);
    sortEachCol(input2dArray);
    var codes = transrateInputs2Codes(input,input2dArray);

	console.log('%s',codes);
}
function transrateInputs2Codes(input,input2dArraySorted){
    var codes="";
    for(var i=1;i<input.length;i++){
        codes +=  transrateInputLine2Code(input[i],input2dArraySorted);
        codes += "\n";
    }
    codes.slice(0,-1);
    return codes;
}
function transrateInputLine2Code(inputLine,input2dArraySorted){
	var tmp = inputLine.split(" ");
    var P = parseInt(tmp[0],10);
    var y = parseInt(tmp[1],10);
    var inputArraySorted = input2dArraySorted[P-1];
    var x = inputArraySorted.indexOf(y)+1;
    return zeroPaddingSixDigit(P) + zeroPaddingSixDigit(x);
}
function sortEachCol(input2dArray){
    for(var i=0;i<input2dArray.length;i++){
        input2dArray[i].sort();
    }
    return;
}

function getInputIn2dArray(input,N,M){
    var input2dArray = init2dArray(N);
    for(var i=0;i<M;i++){
	    var tmp = input[i+1].split(" ");
        if(tmp.length !== 2){
            continue;
        }
        var input2dArrayIndex = parseInt(tmp[0],10)-1;
        var value = parseInt(tmp[1],10);
        input2dArray[input2dArrayIndex].push(value);
    }
    return input2dArray;
}
function init2dArray(N){
    var inputArray = new Array(N);
    for(var i=0;i<N;i++){
        inputArray[i] = [];
    }
    return inputArray;
}
function zeroPaddingSixDigit(num){
    return ('000000' + num).slice(-6)
}

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