
n, m = gets.split.map(&:to_i)

City = Struct.new("City", :i, :p, :y, :id)
cc = Array.new(m)

for i in 0...m
    p, y = gets.split.map(&:to_i)
    cc[i] = City.new(i+1, p, y, 0)
end

cc.sort! do |a,b|
    a.y<=>b.y
end

cnt = Hash.new
cc.each do |c|
    if cnt.has_key?(c.p)
        cnt[c.p] += 1
    else
        cnt[c.p] = 1
    end
    c.id = sprintf("%06d%06d", c.p, cnt[c.p])
end

cc.sort! do |a,b|
    a.i<=>b.i
end

cc.each do |c|
    puts c.id
end
