#include<bits/stdc++.h>
#define reg register
using namespace std;
const int MN=1e5+5;
typedef long long ll;
typedef pair<int,int>pii;
int n,m,a[MN],b[MN];
set<pii>s[MN];
int main(){
	scanf("%d%d",&n,&m);
	for(reg int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		s[x].insert(make_pair(y,i));
	}
	for(reg int i=1;i<=n;i++){
		reg int cnt=1;
		for(set<pii>::iterator it=s[i].begin();it!=s[i].end();it++){
			a[it->second]=i;b[it->second]=cnt;cnt++;
		}
	}
	for(reg int i=1;i<=m;i++)printf("%06d%06d\n",a[i],b[i]);
	return 0;
}