#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
int N , M ;
int P [100000] , Y [100000];
vector <int> yd [100001];
int main (){
	cin >> N >> M;
	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++){
      ll ans=lower_bound(yd[P[i]].begin(),yd[P[i]].end(),Y[i])-yd[P[i]].begin()+1;
      printf ("%012lld\n",ll(P[i])*1000000+ans);
    }
}