unittest
{
	assert( [ "2 3", "1 32", "2 63", "1 12" ].parse.expand.solve == "000001000002\n000002000001\n000001000001" );
	assert( [ "2 3", "2 55", "2 77", "2 99" ].parse.expand.solve == "000002000001\n000002000002\n000002000003" );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nm = input.front.split.to!( long[] );
	auto pyis = new long[ 3 ][ nm[ 1 ] ];
	foreach( i, ref pyi; pyis )
	{
		input.popFront;
		pyi = input.front.split.to!( long[] ) ~ i;
	}
	return tuple( nm[ 0 ], pyis );
}

auto solve( long n, long[ 3 ][] pyis )
{
	auto pcs = new long[ n + 1 ];
	auto rs = new string[ pyis.length ];
	
	foreach( pyi; pyis.sort!( ( x, y ) => x[ 1 ] < y[ 1 ] ) )
	{
		pcs[ pyi[ 0 ] ]++;
		rs[ pyi[ 2 ] ] = format( "%06d%06d", pyi[ 0 ], pcs[ pyi[ 0 ] ] );
	}
	
	return rs.join( "\n" );
}
