#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
using ll = long long;
int main() {
	int n, m; cin >> n >> m;
	int p[m], y[m];
	vector<vector<int>>a(n + 1);
	for (int i = 0; i < m; i++) {
		cin >> p[i] >> y[i];
		a[p[i]].emplace_back(y[i]);
	}
	for (int i = 0; i < n; i++) {
		sort(a[i + 1].begin(), a[i + 1].end());
	}
	for (int i = 0; i < m; i++) {
		printf("%012lld\n",
		ll(p[i]) * 1000000 +
		int(lower_bound(a[p[i]].begin(), a[p[i]].end(), y[i])
			- a[p[i]].begin()) + 1);
	}
}