#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
  	cin>>n>>m;
  	int P[m+1],Y[m+1];
  	map<int,int>mp;
  	map<int,int>cnt;
    vector<pair<int,int>>v;
  	for(int i=0; i<m; i++){
      cin >> P[i] >> Y[i];
      v.push_back(make_pair(P[i],Y[i]));
    }
  	sort(v.begin(),v.end());
  	for(int i=0; i<m; i++){
      mp[v[i].first]++;
      cnt[v[i].second]=mp[v[i].first];
    }
  	for(int i=0; i<m; i++){
      cout << setw(6) << setfill('0') << P[i];
      cout << setw(6) << setfill('0') << cnt[Y[i]]<<endl;  
    }
}
 
