#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main(){
  int n,m;
  cin>>n>>m;
  ll p[m],y[m];
  rep(i,m) cin>>p[i]>>y[i];
  vector<ll> yd[n+1];
  rep(i, m) yd[p[i]].push_back(y[i]);
  rep(i, n) sort(yd[i+1].begin(),yd[i+1].end());
  rep(i, m) printf ("%012lld\n",ll(p[i])*1000000+lower_bound(yd[p[i]].begin(),yd[p[i]].end(),y[i])-yd[p[i]].begin()+1); 
}