function Main(input) {
    input = input.split("\n");
    var nm = input[0].split(" ");
    const n = parseInt(nm[0], 10);
    const m = parseInt(nm[1], 10);
    var citySeries = [];
    for(var i = 1; i <= m; i++){
        var info = input[i].split(" ");
        var pref = parseInt(info[0], 10);
        var year = parseInt(info[1], 10);
        var ord = 0;
        var bizCode = "";
        citySeries.push([i, pref, year, ord, bizCode]);
    }
    citySeries.sort(function(a,b){
         return (a[2]-b[2]);
    });
    citySeries.sort(function(a,b){
        return (a[1]-b[1]);
    });
    for(var i = 0; i < m; i++){
        if(i != 0 && citySeries[i-1][1] == citySeries[i][1]){
            citySeries[i][3] = citySeries[i-1][3] + 1;
        }else{
            citySeries[i][3] = 1;
        }
        var biz = 1000000000000 + 1000000 * citySeries[i][1] + citySeries[i][3];
        citySeries[i][4] =  String(biz).slice(1);
    }
    citySeries.sort(function(a,b){
        return (a[0]-b[0]);
   });
    for(var i = 0; i < m; i++){
        console.log(citySeries[i][4]);
    }
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));