'use strict';

function Main(input) {
  const N = Number(input.split("\n")[0].split(" ")[0]);
  const M = Number(input.split("\n")[0].split(" ")[1]);

  const list = input.split("\n").slice(1).map(x => x.split(" ").map(x => Number(x)));
  const list_sorted = input.split("\n").slice(1).map(x => x.split(" ").map(x => Number(x))).sort((a,b) => a < b ? -1 : 1);

  // console.log(list);
  // console.log(list_sorted);

  const header = [0];
  let previous = 0;
  for(let i = 0; i < M; i++) {
    if(previous !== list_sorted[i][0]) {
      header.push(i);
    }
    previous = list_sorted[i][0];
  }
  // console.log(header);

  const list_rank = [];
  for(let i = 0; i < M; i++) {
    let rank = list_sorted.map(x => x.toString()).indexOf(list[i].toString());
    let minus = header[list[i][0]];
    if(!minus) {
      minus = 0;
    }
    list_rank.push(rank + 1 - minus);
  }


  // console.log(list_rank);

  let digit1 = 0;
  let digit2 = 0;

  for(let i = 0; i < M; i++) {
    digit1 = list[i][0];
    digit2 = list_rank[i];
    const answer = ("000000" + digit1).slice(-6) + ("000000" + digit2).slice(-6);
    console.log(answer);
  }


};

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