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 inputArray = getInputArray(input,N,M);
    sortEachCol(inputArray);
    setCode2InputArray(inputArray);
    sortEachColIndex(inputArray);
	for(var i=0;i<inputArray.length;i++){
        console.log(zeroPaddingSixDigit(inputArray[i].p) + zeroPaddingSixDigit(inputArray[i].code));
    }
}

function setCode2InputArray(inputArraySorted){
    var indexArray = new Array(inputArraySorted.length);
    inputArraySorted.forEach(function(element) {
        var p = element.p;
        indexArray[p] = indexArray[p] === undefined?0:indexArray[p]+1;
        element.code = indexArray[p] + 1;
    });
}
function sortEachCol(inputArray){
    inputArray.sort(function(a,b){
        return a.value - b.value;
    });
}
function sortEachColIndex(inputArray){
    inputArray.sort(function(a,b){
        return a.index - b.index;
    });
}

function getInputArray(input,N,M){
    var inputArray = [];
    for(var i=0;i<M;i++){
	    var tmp = input[i+1].split(" ");
        if(tmp.length !== 2){
            continue;
        }
        var p = parseInt(tmp[0],10);
        var value = parseInt(tmp[1],10);
        inputArray.push({index:i,value:value,p:p});
    }
    return inputArray;
}

function zeroPaddingSixDigit(num){
    return ('000000' + num).slice(-6)
}

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