#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> puni(m);
	map<int, vector<int>> mp;
	for (auto &p : puni)
	{
		cin >> p.first >> p.second;
		mp[p.first].emplace_back(p.second);
	}
	for (auto &p : mp)
	{
		sort(p.second.begin(), p.second.end());
	}
	for (auto &p : puni)
	{
		cout << setw(6) << setfill('0') << p.first << setw(6) << setfill('0') << distance(mp[p.first].begin(), lower_bound(mp[p.first].begin(), mp[p.first].end(), p.second)) + 1 << endl;
	}
	return 0;
}