import std.stdio, std.conv, std.string, std.range, std.typecons, std.format;
import std.algorithm.searching, std.algorithm.sorting, std.algorithm.iteration, std.algorithm.mutation;
// import std.datetime.stopwatch;

void main()
{
    int[] input = readln.split.to!(int[]);
    int N = input[0];
    int M = input[1];
    int[][] prefList;
    Tuple!(int, int)[] cityList;
    prefList.length = N;
    cityList.length = M;
    foreach(i; 0..M)
    {
        input = readln.split.to!(int[]);
        int cityIndex = input[0];
        int cityAge = input[1];
        cityList[i] = tuple!(int, int)(cityIndex-1, cityAge);
        prefList[cityIndex-1] ~= cityAge;
    }
    auto sortedCityFromAgeInPref = prefList.map!sort;
    foreach(city; cityList)
    {
        auto cityID = sortedCityFromAgeInPref[city[0]].lowerBound(city[1]).length+1;
        writeln("%012d".format((city[0]+1)*100000L + cityID));
    }
}
