#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1000000;
vector<int> an[maxn];
int a[maxn],b[maxn];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&a[i],&b[i]);
		an[a[i]].push_back(b[i]);

	}
	for(int i=1;i<=n;i++)
		sort(an[i].begin(),an[i].end());
	for(int i=0;i<m;i++){
		
		int t=lower_bound(an[ a[i] ].begin(),an[a[i]].end(),b[i] )-an[a[i]].begin()+1;
		printf("%06d%06d\n",a[i],t);
	
	}
		
			
	return 0;
}