void main()
{
    long[] tmp = readln.split.to!(long[]);
    long n = tmp[0], m = tmp[1];
    long[] p = new long[m], y = new long[m];
    foreach (i; 0 .. m)
    {
        tmp = readln.split.to!(long[]);
        p[i] = tmp[0], y[i] = tmp[1];
    }

    long[] num = m.iota.array;
    zip(p, y, num).sort!(comp);
    long city = p[0];
    long cnt;
    long[][] id = new long[][](m, 2);
    foreach (i; 0 .. m)
    {
        if (p[i] == city) ++cnt;
        else cnt = 1;

        id[num[i]] = [p[i], cnt];
    }

    foreach (x; id)
    {
        writefln("%06d%06d", x[0], x[1]);
    }
}

alias comp = (x, y) => x[0] == y[0] ? x[1] < y[1] : x[0] < y[0];

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;