function main(input) {
    const lines = input.split('\n');
    const [N, M] = splitNum(lines.shift());
    const ps = (new Array(N+1)).fill(null).map(_ => []);
    const ms = [];
    // generate object for each 市.
    for (let i=0; i<M; i++){
        const [P, Y] = splitNum(lines[i]);
        const mobj = {
            P,
            Y,
            newi: 0,
        };
        ps[P].push(mobj);
        ms.push(mobj);
    }
    // sort 市s in each 県.
    for (const parr of ps) {
        parr.sort((a, b) => a.Y - b.Y);
        // annotate each object with new index.
        let newi = 1;
        for (const p of parr) {
            p.newi = newi++;
        }
    }
    // emit results.
    const pad6l = str => `000000${str}`.slice(-6);
    for (const m of ms) {
        console.log(pad6l(m.P) + pad6l(m.newi));
    }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));
function splitNum(line) {
    return line.split(/\s+/).map(n => parseInt(n));
}