#include "bits/stdc++.h"
using namespace std;
//#define int long long
typedef long long ll;
#define endl '\n'
int mod=1e9+7;

int main(){
  int n,m;
  cin>>n>>m;
  int p[100000];
  int 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++)printf("%012lld\n",ll(p[i])*1000000+int(lower_bound(yd[p[i]].begin(),yd[p[i]].end(),y[i])-yd[p[i]].begin())+1);
}
