#include<bits/stdc++.h>
using namespace std;


int main(){
   int n,m;
   cin>>n>>m;
   int p[100000],y[100000];
   vector<int> yd[100001];

   for (int i = 0; i < m; ++i){
      cin>>p[i]>>y[i];
      yd[p[i]].push_back(y[i]);
   }

   for (int i = 0; i < n; ++i){
      sort(yd[i+1].begin(),yd[i+1].end());
   }
   
   for (int i = 0; i < m; ++i){
      cout<<setfill('0')<<setw(6)<<p[i];
      cout<<setw(6)<<lower_bound(yd[p[i]].begin(),yd[p[i]].end(),y[i])-yd[p[i]].begin()+1;
      cout<<endl;
   }

}
