#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  vector<int> p(m),y(m);
  vector<vector<int>> c(n);
  map<int,pair<int,int>> mp;
  for(int i=0;i<m;i++){
    cin >> p[i] >> y[i];
    c[p[i]-1].push_back(y[i]);
  }
  for(int i=0;i<n;i++){
    sort(c[i].begin(),c[i].end());
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<c[i].size();j++){
      mp[c[i][j]]=make_pair(i+1,j+1);
    }
  }
  for(int i=0;i<m;i++){
    printf("%06d%06d\n",mp[y[i]].first,mp[y[i]].second);
  }
}