def find_cr(arr, i)
    cnt = 0
    arr.each do |a|
        rank = 1
        a.each do |b|
            return [cnt,rank] if b[0] == i
            rank += 1
        end
        cnt += 1
    end
end

def cc
    n,m = gets.chomp.split(/\s/).map{|x| x.to_i}

    #py = {}
    #for i in 0..(n)
    #    py[i] = []
    #end

    py = []
    for i in 0..(n)
        py[i] = []
    end

    for i in 1..m
        pr, y = gets.chomp.split(/\s/).map{|x| x.to_i}
        py[pr].push([i-1, y])
        #py[pr].push([i-1, y])
    end

    for i in 0..(n)
        py[i] = py[i].sort {|a,b| (a[1] <=> b[1]).nonzero? || a[2] <=> b[2]}
    end
    #p py
    #p py.sort {|a,b| a[1].sort {|c,d| c[1]<=>d[1]} > b[1] }
    #p py.sort {|a,b| (a[1] <=> b[1]).nonzero? || a[2] <=> b[2]}

    for i in 0..(n)
        c,r = find_cr(py, i)
        print sprintf("%06d%05d\n",c, r)
    end
end

cc