#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"I=lambda:list(map(int,input().split()[::-1]))\n"
"m,n=I()\n"
"c=[0]*-~n\n"
"a=[0]*m\n"
"for y,p,i in sorted(I()+[i]for i in range(m)):\n"
"  c[p]+=1\n"
"  a[i]='%06d%06d'%(p,c[p])\n"
"print('\n'.join(a))\n"
"\"";
  system(s);
  return 0;
}            