"use strict";
function Main(input) {
    let lines = input.split("\n");
    let nm = lines.shift().split(/\s/).map((v) => v - 0);
    let N = nm[0], M = nm[1];
    let PY = new Array(M);
    for (let m = 0; m < M; m++) {
        PY[m] = lines.shift().split(/\s/).map((v) => v - 0).concat([m]);
    }
    PY.sort((a, b) => (a[0] <= b[0] ? a[1] - b[1] : a[0] - b[0]));
    let p = -1, q = 0;
    for (let m = 0; m < M; m++) {
        if (PY[m][0] == p) PY[m][1] = ++q;
        else {
            p = PY[m][0];
            q = 0;
            PY[m][1] = ++q;
        }
    }
    PY.sort((a, b) => a[2] - b[2]);
    const d6 = (n) => ('000000' + n.toString()).slice(-6);
    const d12 = (v) => d6(v[0]) + d6(v[1]);
    for (let m = 0; m < M; m++) {
        console.log(d12(PY[m]));
    }
}
if (typeof window == "undefined") Main(require("fs").readFileSync("/dev/stdin", "utf8"));
