import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons;

void main() {
    auto tmp = readln.split.to!(long[]);
    const N = tmp[0], M = tmp[1];

    class City {long p, index, year, order; }
    City[] cityList;
    foreach (i; 0..M) {
        tmp = readln.split.to!(long[]);
        const P = tmp[0], Y = tmp[1];
        auto c = new City;
        c.p = P;
        c.index = i;
        c.year = Y;
        cityList ~= c;
    }
    foreach (i; 0..N+1) {
        cityList
            .filter!(c => c.p == i)
            .array
            .sort!((a,b) => a.year < b.year)
            .enumerate
            .array
            .each!(c => c.value.order = c.index);
    }
    cityList.each!(c => writefln("%06d%06d",c.p, c.order+1));
}
