using System;

using System.Text;

using System.Linq;

using System.Collections;

using System.Collections.Generic;

using static System.Console;

using static System.Math;



namespace AtCoder

{

    public class Program

    {

        public static void Main(string[] args)

        {

            new Program().Solve(new ConsoleInput(Console.In, ' '));

        }

        class P : IComparable{
            public int _p, _y, _i;
            public P(int p,int y,int i)
            {
                _p = p;
                _y = y;
                _i = i;
            }

            public int CompareTo(object obj)
            {
                var sp = obj as P;
                if(_p != sp._p)
                {
                    return _p - sp._p;
                }
                return _y - sp._y;
            }
        }
        public void Solve(ConsoleInput cin)

        {

            // 解答はココに書く
            int n, m;
            n = cin.ReadInt;
            m = cin.ReadInt;

            string []res = new string[m];
            var list = new List<P>();
            for (int i = 0; i < m; i++)
            {
                int p, y;
                p = cin.ReadInt;
                y = cin.ReadInt;
                list.Add(new P(p, y, i));
            }

            list.Sort();
            var c = 1;
            var pi = 0;
            for (int i = 0; i < list.Count(); i++)
            {
                if(pi != list[i]._p)
                {
                    c = 1;
                    pi = list[i]._p;
                }
                res[list[i]._i] = list[i]._p.ToString().PadLeft(6, '0') + c.ToString().PadLeft(6, '0');
                c++;
            }

            for (int i = 0; i < m; i++)
            {
                WriteLine(res[i]);
            }
        }

    }


    public class ConsoleInput

    {

        private readonly System.IO.TextReader _stream;

        private char _separator = ' ';

        private Queue<string> inputStream;

        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')

        {

            this._separator = separator;

            this._stream = stream;

            inputStream = new Queue<string>();

        }

        public string Read

        {

            get

            {

                if (inputStream.Count != 0) return inputStream.Dequeue();

                string[] tmp = _stream.ReadLine().Split(_separator);

                for (int i = 0; i < tmp.Length; ++i)

                    inputStream.Enqueue(tmp[i]);

                return inputStream.Dequeue();

            }

        }

        public string ReadLine { get { return _stream.ReadLine(); } }

        public int ReadInt { get { return int.Parse(Read); } }

        public long ReadLong { get { return long.Parse(Read); } }

        public double ReadDouble { get { return double.Parse(Read); } }

        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }

        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }

        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }

    }

}

Measured memory_bytes: 31144