import std.stdio, std.string, std.array, std.conv, std.algorithm, std.math;

class City{
	int id;
	int pref;
	int year;
	string answer;
	this(int id, int p, int y){
		this.id = id, this.pref = p, this.year = y;
	}
	bool isYoungerThan(City city){
		if(this.pref < city.pref) return 1;
		else if(this.year < city.year) return 1;
		return 0;
	}
}

void main(){
	int[] tmp;
	tmp = readln.chomp.split.map!(to!int).array;
	int n = tmp[0], m = tmp[1];
	City[] cities;
	
	for(int i = 0; i < m; i ++){
		tmp = readln.chomp.split.map!(to!int).array;
		int p = tmp[0], y = tmp[1];
		cities ~= new City(i, p, y);
	}
	
	cities.sort!"a.isYoungerThan(b)"();
	
	int x = -1;
	int p = -1;
	for(int i = 0; i < m; i ++){
		City city = cities[i];
		if(p != city.pref) x = 1; else x += 1;
		city.answer = ("000000" ~ city.pref.to!string)[$ - 6 .. $] ~ ("000000" ~ x.to!string)[$ - 6 .. $];
	}
	
	cities.sort!"a.id < b.id"();
	
	for(int i = 0; i < m; i ++){
		cities[i].answer.writeln;
	}
	
}