N,M=gets.split.map(&:to_i)
PY=M.times.map{gets.split.map(&:to_i)}

data=Array.new(N){[]}
M.times do |i|
    city_id = i
    prefe_id, year = PY[i]
    data[prefe_id-1] << [year, city_id]
end

N.times {|prefe_id| data[prefe_id].sort_by!{|year,_| year}}

ans=Array.new(M)
N.times do |prefe_id|
    data[prefe_id].size.times do |id|
        _, city_id = data[prefe_id][id]
        ans[city_id] = sprintf("%06d", prefe_id+1) + sprintf("%06d", id+1)
    end
end

puts ans
