import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 1_000_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "x", long, "y", long, "z");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

void main()
{
    long n, m;
    scan(n, m);
    auto id = new Pair[](m);
    foreach (i; iota(m))
    {
        long p, y;
        scan(p, y);
        id[i] = Pair(p, y, i);
    }
    id.sort!"a.x == b.x ? a.y < b.y : a.x < b.x"();
    long iter;
    foreach (i; iota(n))
    {
        long tmp;
        while (iter < m && id[iter].x == i + 1)
        {
            id[iter].y = tmp++;
            iter++;
        }
    }
    // id.each!(x => x.writeln());
    id.sort!"a.z < b.z"();
    foreach (i; iota(m))
    {
        writef("%06s", id[i].x);
        writefln("%06s", id[i].y + 1);
    }
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}
