using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using static System.Console;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        int[] NM = ReadLineParseIntArray();
        int N = NM[0];
        int M = NM[1];
        List<Tuple<int, int>>[] tuples = new List<Tuple<int, int>>[N];
        for (int i = 0; i < N; i++)
            tuples[i] = new List<Tuple<int, int>>();
        for(int i = 0; i < M; i++)
        {
            int[] py = ReadLineParseIntArray();
            tuples[py[0] - 1].Add(new Tuple<int, int>(py[1], i));
        }
        PriorityQueue<ComparablePair<int, long>> priorityQueue = new PriorityQueue<ComparablePair<int, long>>(M);
        for(int i = 0; i < N; i++)
        {
            if (tuples[i].Count == 0) continue;

            tuples[i].Sort((a, b) => a.Item1.CompareTo(b.Item1));
            int iter = 1;
            foreach(var v in tuples[i])
            {
                priorityQueue.Push(new ComparablePair<int, long>(v.Item2, (i + 1) * 1000000L + iter++));
            }
        }
        for(int i = 0; i < M; i++)
        {
            WriteLine($"{priorityQueue.Pop().Item2:000000000000}");
        }
    }

    static int ReadLineParseInt() => int.Parse(ReadLine());
    static int[] ReadLineParseIntArray() => ReadLine().Split(' ').Select(int.Parse).ToArray();
        public class PriorityQueue<T> where T : IComparable
    {
        private IComparer<T> _comparer = null;
        private int _type = 0;

        private T[] _heap;
        private int _size = 0;

        private int _count = 0;

        ///<summary>
        ///Priority Queue with custom comparer
        /// </summary>
        public PriorityQueue(int maxSize, IComparer<T> comparer)
        {
            _heap = new T[maxSize];
            _comparer = comparer;
        }

        ///<summary>
        ///Priority queue
        ///</summary>
        ///<param name="maxSize">max size</param>
        ///<param name="type">0: asc, 1:desc</param>
        public PriorityQueue(int maxSize, int type = 0)
        {
            _heap = new T[maxSize];
            _type = type;
        }

        private int Compare(T x, T y)
        {
            if (_comparer != null) return _comparer.Compare(x, y);
            return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
        }

        public void Push(T x)
        {
            _count++;

            //node number
            var i = _size++;

            while (i > 0)
            {
                //parent node number
                var p = (i - 1) / 2;

                if (Compare(_heap[p], x) <= 0) break;

                _heap[i] = _heap[p];
                i = p;
            }

            _heap[i] = x;
        }

        public T Pop()
        {
            _count--;

            T ret = _heap[0];
            T x = _heap[--_size];

            int i = 0;
            while (i * 2 + 1 < _size)
            {
                //children
                int a = i * 2 + 1;
                int b = i * 2 + 2;

                if (b < _size && Compare(_heap[b], _heap[a]) < 0)
                    a = b;

                if (Compare(_heap[a], x) >= 0)
                    break;

                _heap[i] = _heap[a];
                i = a;
            }

            _heap[i] = x;

            return ret;
        }

        public int Count() { return _count; }
        public T Peek() { return _heap[0]; }
        public bool Contains(T x)
        {
            for (int i = 0; i < _size; i++)
                if (x.Equals(_heap[i]))
                    return true;
            return false;
        }
        public void Clear() { while (this.Count() > 0) this.Pop(); }
        public IEnumerator<T> GetEnumerator()
        {
            var ret = new List<T>();
            while(this.Count() > 0)
            {
                ret.Add(this.Pop());
            }
            foreach(var r in ret)
            {
                this.Push(r);
                yield return r;
            }
        }
        public T[] ToArray()
        {
            T[] array = new T[_size];
            int i = 0;
            foreach(var r in this)
            {
                array[i++] = r;
            }
            return array;
        }
    }

  public class ComparablePair<T, U> : IComparable where T : IComparable<T>
    {
        public readonly T Item1;
        public readonly U Item2;

        public int CompareTo(object obj)
        {
            ComparablePair<T, U> castedObj = (ComparablePair<T, U>)obj;
            return this.Item1.CompareTo(castedObj.Item1);
        }

        public ComparablePair(T t, U u)
        {
            Item1 = t;
            Item2 = u;
        }
    }
}

Measured memory_bytes: 34416