#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>

using namespace std;

int main(){
	int i, j;
	int n, m, p, y;

	struct MyStruct
	{
		int num;
		//vector<int>list;
		vector < pair<int, int>>list;
	};

	

	cin >> n >> m;
	//cin >> p >> y;

	//map<int, int>mp;
	vector<pair<int, int>>list, list2;
	vector<tuple<int, int, int>> t,t2;


	for (i = 0; i < m; i++) {
		int num1, num2;
		cin >> num1 >> num2;
		list.push_back(make_pair(num1, num2));
		t.push_back(make_tuple(num1, num2, i));
		list2.push_back(make_pair(num1, num2));
	}

	sort(list.begin(), list.end());
	sort(t.begin(), t.end());

	int nnn = get<0>(t[0]);
	int rank = 1;

	for (i = 0; i < m; i++) {
		if (nnn == get<0>(t[i])) {
			t2.push_back(make_tuple(get<2>(t[i]), get<0>(t[i]), rank));
			rank++;
		}
		else {
			nnn = get<0>(t[i]);
			rank = 1;
			t2.push_back(make_tuple(get<2>(t[i]), get<0>(t[i]), rank));
			rank++;
		}
	}

	sort(t2.begin(), t2.end());


	for (i = 0; i < m; i++) {
		int num1 = get<1>(t2[i]);
		int num2 = get<2>(t2[i]);

		cout << setw(6) << setfill('0') << num1 << setw(6) << setfill('0') << num2 << endl;
	}

	getchar();
	getchar();
	return 0;

	//vector<MyStruct>aaa;
	map<int, MyStruct>bbb;
	//int no = list[0].first;
	int jyun = 1;

	for (i = 0; i < m; i++) {
		
		if (bbb.count(list[i].first) == 0) {
			jyun = 1;
			MyStruct st;
			st.num = list[i].first;
			st.list.push_back(make_pair(list[i].second, jyun));
			jyun++;
			bbb.insert(make_pair(list[i].first, st));
		}
		else {
			//MyStruct st;
			//st.num = list[i].first;
			bbb[list[i].first].list.push_back(make_pair(list[i].second, jyun));
			jyun++;
			//bbb.insert(make_pair(list[i].first, st));

		}
	}


	/*sort(t.begin(), t.end());
	vector<int>jun;
	

	int cnt = 1;
	int num1 = get<0>(t[i]);

	for (i = 0; i < m; i++) {
		if (num1 == get<0>(t[i])) {
			get<2>(t[i]) = cnt;
			cnt++;
		}
		else {
			cnt = 1;
			num1 = get<0>(t[i]);
			get<2>(t[i]) = cnt;
			cnt++;
		}


	}*/


	for (i = 0; i < m; i++) {
		int num1 = list2[i].first;
		int num2 = list2[i].second;
		int num3;
		int count = 1;
		bool flag2 = false;
		if (bbb[num1].list.size() >= 5000) {
			count = 300;
		}
		if (bbb[num1].list.size() >= 1000) {
			count = 100;
		}
		if (bbb[num1].list.size() >= 500) {
			count = 5;
		}

		for (j = 0; j < bbb[num1].list.size(); j+=count) {
			//auto result = find(bbb[num1].list._Myfirst.begin(), bbb[num1].list._Myfirst.end(), num2 );
			/*if (result == v.end()) {
				std::cout << "not found" << std::endl;
			}
			else {*/
				//std::cout << "found: " << (*result).second << std::endl;
			//}

			if (num2 == bbb[num1].list[j].first) {
				num3 = bbb[num1].list[j].second;
				flag2 = true;
				break;
			}

			if (num2 < bbb[num1].list[j].first) {
				bool flag3 = false;
				for (int k = j; k >= 0; k--) {
					if (num2 == bbb[num1].list[k].first) {
						num3 = bbb[num1].list[k].second;
						flag2 = true;
						flag3 = true;
						break;
					}
				}
				break;

			}
		}

		if (flag2 == false) {
			for (int k = bbb[num1].list.size()-1; k >= 0; k--) {
				if (num2 == bbb[num1].list[k].first) {
					num3 = bbb[num1].list[k].second;
					flag2 = true;
					break;
				}
			}
		}
		
		cout << setw(6) << setfill('0') << num1 << setw(6) << setfill('0') << num3 << endl;
	}







	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 5604