import std.stdio, std.math, std.algorithm, std.array, std.string, std.conv, std.container, std.range;
T Read(T)() { return readln.chomp.to!(T); }
T[] Reads(T)() { return readln.split.to!(T[]); }
alias read = Read!(int);
alias reads = Reads!(int);

struct Info {
    int p, y;
}


int bsearch(T)(T[] a, int x) {
    int n = a.length.to!int;
    int lb = -1, rb = n;
    while (rb - lb > 1) {
        int mid = lb + (rb - lb) / 2;
        if (a[mid] >= x) rb = mid;
        else lb = mid;
    }
    return rb;
}

void main() {
    int n, m; readf("%d %d\n", &n, &m);
    auto city = new Info[m];
    int[][] ys = new int[][](n);
    foreach (ref c ; city) {
        readf("%d %d\n", &c.p, &c.y);
        ys[c.p - 1] ~= c.y;
    }

    foreach (ref y ; ys) sort(y);

    foreach (c; city) {
        int rnk = bsearch(ys[c.p - 1], c.y) + 1;
        writefln("%06s%06s", c.p, rnk);
    }
}