#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

vector<pair<int,int>>pairs;
int main(){
  int N,M;cin>>N>>M;
  vector<int> Ken[120000];
  int P[120000],Y[120000];
  for(int i=0;i<M;i++){
    cin>>P[i]>>Y[i];
    Ken[P[i]].push_back(Y[i]);
  }
  for(int i=0;i<N;i++){
    sort(Ken[i+1].begin(),Ken[i+1].end());
  }
  for(int i=0;i<M;i++){
    printf("%06d",P[i]);
    printf("%06d\n",int(lower_bound(Ken[P[i]].begin(),Ken[P[i]].end(),Y[i])-Ken[P[i]].begin())+1);
  }


}