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;

void main()
{
    int[] input = readln.split.to!(int[]);
    int N = input[0];
    int M = input[1];
    Tuple!(int,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] ~= cityList[i];
    }

    int[Tuple!(int,int)] cityIDList;
    foreach(pref; prefList)
    {
        foreach(i,city; enumerate(pref.sort!((a,b)=>a[1]<b[1])()))
        {
            cityIDList[city] = cast(int)i;
        }
    }
    foreach(i; 0..cityList.length)
    {
        writeln("%06d%06d".format(cityList[i][0]+1, cityIDList[cityList[i]]));
    }
}
