'use strict';
const main = input => {
  const n = parseInt(input[0].split(' ')[0]), m = parseInt(input[0].split(' ')[1]);
  input.shift();
  // console.log(input);
  
  let py = new Array(m);
  for(let i=0; i<m; i++) {
    py[i] = new Array(4).fill(0);
    input[i] = input[i].split(' ').map(val => parseInt(val, 10));
    py[i] = [input[i][0], input[i][1], i, 0];
  }
  
  // console.log(py);
  py.sort((a,b) => b[0]-a[0]>0?-1:a[0]-b[0]>0?1:b[1]-a[1]>0?-1:a[1]-b[1]>0?1:0);
  // console.log(py);
  let count = 1;
  for(let i=0; i<m-1; i++) {
    py[i][3] = count;
    if (py[i][0]==py[i+1][0]) {
      count++;
    } else {
      count = 1;
    }
  }
  py[m-1][3] = count;
  // console.log(py);
  py.sort((a,b) => b[2]-a[2]>0?-1:a[2]-b[2]>0?1:0);
  // console.log(py);
  for(let i=0; i<m; i++) {
    console.log(("000000"+py[i][0]).slice(-6) + ("000000"+py[i][3]).slice(-6));
    
  }
}
main(require("fs").readFileSync("/dev/stdin", "utf8").split('\n'));