using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Contest
{
	public static void Main()
	{

/*
		int n = a[0];
		int[][] e;
		MyIO.ReadMatrix(n, out e);

		int[] a;
		MyIO.ReadArray(out a);

		Tuple<int,int>[] p;
		MyIO.ReadLines(n, out p);

        long a,b,c,d,e,f;
        MyIO.ReadMulti(out a, out b, out c, out d, out e, out f);

		MyIO.WriteArray(ans);
*/

        int n,m;
		Tuple<int,int>[] p;
		MyIO.ReadMulti(out n, out m);
		MyIO.ReadLines(m, out p);

		Tuple<int,int,int>[] e = new Tuple<int, int, int>[m]; 
		for(int i=0; i<m; i++) e[i] = new Tuple<int, int, int>(p[i].Item1, p[i].Item2, i);

		Array.Sort(e,(x,y)=>(x.Item2-y.Item2));
 
		string[] ss = new string[m];
		int[] ccnt = new int[n+1];
		foreach(Tuple<int, int, int> t in e) ss[t.Item3] = String.Format("{0:D6}{1:D6}", t.Item1, ++ccnt[t.Item1]);



		MyIO.WriteLines(ss);

	}



}

public class Printer : System.IO.StreamWriter
{
	public override IFormatProvider FormatProvider { get { return System.Globalization.CultureInfo.InvariantCulture; } }
	public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
	public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
}
public static class MyIO
{
	private static char[] splitter = new char[] {' '};
	private static bool eq<T, U>() => typeof(T).Equals(typeof(U));
	private static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
	private static T cv<T>(string s) => eq<T, int>()    ? ct<T, int>(int.Parse(s))
	                                  : eq<T, long>()   ? ct<T, long>(long.Parse(s))
	                                  : eq<T, double>() ? ct<T, double>(double.Parse(s, System.Globalization.CultureInfo.InvariantCulture))
	                                  : eq<T, char>()   ? ct<T, char>(s[0])
	                                                    : ct<T, string>(s);
	public static string[] ReadArray<T>(out T[] a) {		
		var ar = Console.ReadLine().Split(splitter, StringSplitOptions.RemoveEmptyEntries); 												
		a = System.Array.ConvertAll(ar, new Converter<string,T>(cv<T>));
		return ar;
	}										
	public static string[] ReadMulti<T>(out T a) {
		var ar = Console.ReadLine().Split(splitter, StringSplitOptions.RemoveEmptyEntries); 
		a = cv<T>(ar[0]);
		return ar;
	}
	public static string[] ReadMulti<T, U>(out T a, out U b) {
		var ar = ReadMulti<T>(out a); 
        b = cv<U>(ar[1]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V>(out T a, out U b, out V c) {
		var ar = ReadMulti<T, U>(out a, out b); 
        c = cv<V>(ar[2]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V, W>(out T a, out U b, out V c, out W d) {
		var ar = ReadMulti<T, U, V>(out a, out b, out c); 
        d = cv<W>(ar[3]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e) {
		var ar = ReadMulti<T, U, V, W>(out a, out b, out c, out d); 
        e = cv<X>(ar[4]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V, W, X, Y>(out T a, out U b, out V c, out W d, out X e, out Y f) {
		var ar = ReadMulti<T, U, V, W, X>(out a, out b, out c, out d, out e); 
        f = cv<Y>(ar[5]);
		return ar;
	}
	public static string[][] ReadMatrix<T>(int n, out T[][] a) {
		a = new T[n][];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) arr[i] = ReadArray(out a[i]);
		return arr;
	}
	public static string[][] ReadLines<T>(int n, out T[] a) {
		a = new T[n];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) arr[i] = ReadMulti(out a[i]);
		return arr;
	}
	public static string[][] ReadLines<T, U>(int n, out Tuple<T, U>[] a) {
		a = new Tuple<T, U>[n];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) {
			T o; U p;
			arr[i] = ReadMulti(out o, out p);
			a[i] = new Tuple<T, U>(o, p);
		}
		return arr;
	}
	public static string[][] ReadLines<T, U, V>(int n, out Tuple<T, U, V>[] a) {
		a = new Tuple<T, U, V>[n];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) {
			T o; U p; V q;
			arr[i] = ReadMulti(out o, out p, out q);
			a[i] = new Tuple<T, U, V>(o, p, q);
		}
		return arr;
	}

	private static void wwp(Action act){
		var sw = new Printer(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(sw);
		act();
		Console.Out.Flush();
		sw.AutoFlush = true;
		Console.SetOut(sw);
	}
	public static void WriteMulti(params object[] a) {
		wwp(()=>{
			foreach(object x in a) Console.Write("{0} ", x);
			Console.WriteLine("");
		});
	}
	public static void WriteArray<T>(T[] a) {
		wwp(()=>{
			foreach(T x in a) Console.Write("{0} ", x);
			Console.WriteLine("");
		});
	}
	public static void WriteLines<T>(T[] a) {
		wwp(()=>{
			foreach(T x in a) Console.WriteLine(x);
		});
	}

}



Measured memory_bytes: 39556