#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;

int P[100000], Y[100000];
vector<int> yd[100001];

int main()
{
	int N, M; 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++)
		printf("%012lld\n", ll(P[i]) * 1000000 + int(lower_bound(yd[P[i]].begin(),
			yd[P[i]].end(), Y[i]) - yd[P[i]].begin()) + 1);

	return 0;
}
