"use strict"

function Main(input) {
  let args = input.split("\n");

  let NM = args[0].split(" ");

  let N = parseInt(NM[0], 10);
  let M = parseInt(NM[1], 10);

  args.shift();
  args.pop();

  let citys = args.map((e, i) => {
    let cityInfo = e.split(" ").map(e => parseInt(e));
    return [i, cityInfo[0], cityInfo[1]]
  });

  citys.sort((a, b) => (a[2] - b[2]));

  let countryCount = Array(N + 1).fill(1);

  citys.forEach((e) => {
    e[3] = ('000000' + e[1]).slice(-6) + ('000000' + countryCount[e[1]]).slice(-6);
    countryCount[e[1]]++;
  });

  citys.sort((a, b) => (a[0] - b[0]));

  let result = '';
  citys.forEach(e => result += (e[3] + '\n'));
  console.log(result.trim());
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));