"use strict";
function main(input) {
  const inputs = input.split("\n").filter(x => x !== "");

  const N = Number(inputs[0].split(" ")[0]);
  const M = Number(inputs[0].split(" ")[1]);
  
  const arr = [];

  for (let i = 0; i < M; i++) {
    const inputLine = inputs[1+i].split(" ");
    const P = inputLine[0];
    const Y = inputLine[1];
    arr.push({
      index: i,
      P,
      Y
    })
  }

  const mapArr = {};

  arr.forEach(element => {
    if (mapArr[element.P]) {
      mapArr[element.P].push(element);
    } else {
      mapArr[element.P] = [element];
    }
  })

  let result = [];
  for (let P in mapArr) {
    mapArr[P] = mapArr[P].sort((a,b) => a.Y-b.Y);
    mapArr[P] = mapArr[P].map((element, index) => {
      let firstHalf = "" + P;
      while (firstHalf.length < 6) {
        firstHalf = "0" + firstHalf;
      }
      let secondHalf = "" + (index + 1);
      while (secondHalf.length < 6) {
        secondHalf = "0" + secondHalf;
      }

      return Object.assign({}, element, {id: firstHalf + secondHalf});
    });

    result = result.concat(mapArr[P]);
  }

  result = result.sort((a,b) => a.index - b.index)

  console.log(result.map(x => x.id).reduce((acc, cur) => {
    return acc + cur + "\n"
  }, ""));

}

main(require("fs").readFileSync("/dev/stdin", "utf8"));
