#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

vector<int> d[101010];

signed main() {
  int n,m; cin>>n>>m;
  vector<int> p(m),y(m);
  for(int i=0;i<m;++i){
    cin>>p[i]>>y[i];
    d[p[i]].push_back(y[i]);    
  }
  for(int i=0;i<101010;++i){
    sort(d[i].begin(), d[i].end());
  }
  for(int i=0;i<m;++i){
    printf("%06ld%06ld\n", p[i], lower_bound(d[p[i]].begin(), d[p[i]].end(), y[i]) - d[p[i]].begin() + 1);
  }
  return 0;
}
