#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

using namespace std;

/////////////         qsortのラッピング
class sortClass {
public:
	sortClass() {
		data = 0;
		ptr = NULL;
	}
	double data;//並び替え用
	void *ptr;//付随して動くデータ
};
int qsort_int_compare_ascend(const void *a, const void *b) {
	return *(int*)a - *(int*)b;
}
int qsort_int_compare_descend(const void *a, const void *b) {
	return *(int*)b - *(int*)a;
}
int qsort_class_compare_ascend(const void *a, const void *b) {
	double c = ((sortClass*)a)->data - ((sortClass*)b)->data;
	if (c > 0.00001) { return 1; }
	if (c > -0.00001) { return 0; }
	return -1;
}
int qsort_class_compare_descend(const void *a, const void *b) {
	double c = ((sortClass*)b)->data - ((sortClass*)a)->data;
	if (c > 0.00001) { return 1; }
	if (c > -0.00001) { return 0; }
	return -1;
}

void ascendOrder(int size, int *array) {//sho-jun
	qsort(array, size, sizeof(int), qsort_int_compare_ascend);
}
void descendOrder(int size, int *array) {//ko-jun
	qsort(array, size, sizeof(int), qsort_int_compare_descend);
}
void ascendOrder(int size, int *data, void **array) {//sho-jun
	sortClass *S = new sortClass[size];
	for (int i = 0; i < size; i++) {
		S[i].data = data[i];
		S[i].ptr = array[i];
	}
	qsort(S, size, sizeof(sortClass), qsort_class_compare_ascend);
	for (int i = 0; i < size; i++) {
		data[i] = S[i].data;
		array[i] = S[i].ptr;
	}
	delete[] S;
}
void descendOrder(int size, int *data, void **array) {//sho-jun
	sortClass *S = new sortClass[size];
	for (int i = 0; i < size; i++) {
		S[i].data = data[i];
		S[i].ptr = array[i];
	}
	qsort(S, size, sizeof(sortClass), qsort_class_compare_descend);
	for (int i = 0; i < size; i++) {
		data[i] = S[i].data;
		array[i] = S[i].ptr;
	}
	delete[] S;
}
void getAscendOrder(int size, int *data, int *dest) {//昇順の順番を得る
	sortClass *S = new sortClass[size];
	for (int i = 0; i < size; i++) {
		S[i].data = data[i];
		S[i].ptr = &dest[i];
	}
	qsort(S, size, sizeof(sortClass), qsort_class_compare_ascend);
	for (int i = 0; i < size; i++) {
		*(int*)(S[i].ptr) = i;
	}
	delete[] S;
}
void getDescendOrder(int size, int *data, int *dest) {//降順の順番を得る
	sortClass *S = new sortClass[size];
	for (int i = 0; i < size; i++) {
		S[i].data = data[i];
		S[i].ptr = &dest[i];
	}
	qsort(S, size, sizeof(sortClass), qsort_class_compare_descend);
	for (int i = 0; i < size; i++) {
		*(int*)(S[i].ptr) = i;
	}
	delete[] S;
}


int main() {
	int N, M;
	cin >> N >> M;

	int *P = new int[M];
	int *Y = new int[M];
	int *num = new int[N]; for (int i = 0; i < N; i++) { num[i] = 0; }
	int **x = new int*[N];
	int **d = new int*[N];

	for (int i = 0; i < M; i++) {
		cin >> P[i] >> Y[i];
		num[P[i] - 1]++;
	}

	for (int i = 0; i < N; i++) {
		x[i] = new int[num[i]];
		d[i] = new int[num[i]];
		for (int k = 0; k < num[i]; k++) {
			x[i][k] = 0;
		}
		num[i] = 0;
	}

	for (int i = 0; i < M; i++) {
		x[P[i] - 1][num[P[i] - 1]] = Y[i];
		num[P[i] - 1]++;
	}

	for (int i = 0; i < N; i++) {
		getAscendOrder(num[i], x[i], d[i]);
		num[i] = 0;
	}


	char string[7] = {};
	for (int i = 0; i < M; i++) {
		int n = P[i] - 1;
		int f = n + 1;
		for (int k = 5; k >= 0; k--) {
			string[k] = '0'+f % 10; f /= 10;
		}
		cout << string;

		f = d[n][num[n]]+1;
		for (int k = 5; k >= 0; k--) {
			string[k] = '0' + f % 10; f /= 10;
		}
		cout << string<<endl;
		num[n]++;
	}

	for (int i = 0; i < N; i++) {
		delete[] x[i];
		delete[] d[i];
	}
	delete[] x;
	delete[] d;
	delete[] num;
	delete[] P;
	delete[] Y;
	return 0;
}

Measured memory_bytes: 12796