import std.stdio, std.string, std.conv;
import std.typecons;
import std.algorithm, std.array, std.range, std.container;
import std.math;

void main() {
	auto data = readln.split;
	auto N = data[0].to!int, M = data[1].to!int;
	
	alias City = Tuple!(int, "i", int, "p", int, "y");
	City[] cities;
	foreach (i; 0 .. M) {
		data = readln.split;
		cities ~= City(i, data[0].to!int, data[1].to!int);
	}
	cities = sort!((a,b) => a.p<b.p || a.p==b.p && a.y < b.y)(cities).array;
	
	int x, prefecture;
	Tuple!(int, "i", string, "id")[] result;
	foreach (city; cities) {
		if (city.p != prefecture) x = 1, prefecture = city.p;
		else ++x;
		result ~= Tuple!(int, "i", string, "id")(city.i, to_str(city.p) ~ to_str(x));
	}
	sort!((a,b) => a.i < b.i)(result).each!(x => x.id.writeln);
	
}

string to_str(int n) {
	auto result = n.to!string;
	if (result.length < 6) result = "0".repeat(6-result.length).reduce!"a~b" ~ result;
	return result;
}