import std.stdio;
import std.algorithm;
import std.conv;
import std.datetime;
import std.numeric;
import std.math;
import std.string;

string my_readln() { return chomp(readln()); }

void main()
{//try{
	auto tokens = split(my_readln());
	auto N = to!ulong(tokens[0]);
	auto M = to!ulong(tokens[1]);

	ulong[] P, Y;
	P.length = cast(uint)M;
	Y.length = cast(uint)M;
	ulong[][] county;
	county.length = cast(uint)N;
	foreach (i; 0..M)
	{
		auto tokens2 = split(my_readln());
		P[cast(uint)i] = to!ulong(tokens2[0]) - 1;
		Y[cast(uint)i] = to!ulong(tokens2[1]);
		county[cast(uint)P[cast(uint)i]] ~= cast(ulong)i;
	}

	foreach (ref e; county)
	{
		if (e.length == 0) continue;
		sort!((ulong a, ulong b){ return Y[cast(uint)a] < Y[cast(uint)b]; })(e);
	}

	ulong digit(ulong x)
	{
		ulong d;
		while (x)
		{
			x /= 10;
			++d;
		}
		return d;
	}

	string[] zero = ["000000", "00000", "0000", "000", "00", "0", ""];

	foreach (i, e; P)
	{
		write(zero[cast(uint)digit(e+1)] ~ to!string(e+1));

		auto c = county[cast(uint)e];
		auto pos = countUntil(c, i) + 1;
		writeln(zero[cast(uint)digit(pos)] ~ to!string(pos));
	}

	stdout.flush();
/*}catch (Throwable e)
	{
		writeln(e.toString());
	}
readln();*/
}