#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int M = 1e5 + 10;
int b[M][2];
vector<long long> a[M];
int main(){

	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int p,y;
		cin>>p>>y;
		a[p].push_back(y); 
		b[i][0] = p;
		b[i][1] = y;
	}
	for(int i=1;i<=n;i++){
		sort(a[i].begin(),a[i].end());
	}
	for(int i=0;i<m;i++){
		int p,y;
		p = b[i][0];
		y = b[i][1];
		int rank;
		rank = find(a[p].begin(),a[p].end(),y)-a[p].begin();
		printf("%06d%06d\n",p,rank);
	}
	return 0;
}