n, m = gets.split.map(&:to_i)
x = Array.new(m)
y = Array.new(m)
idxs = Array.new(m)
cnt = Array.new(n, 1)

m.times do |i|
    x[i], y[i] = gets.split.map(&:to_i)
    idxs[i] = i
end

idxs.sort_by!{|i| y[i]}

ans = Array.new(m)
m.times do |i|
   ii = idxs[i]
   ans[ii] = ("%06d" % x[ii]) + ("%06d" % (cnt[x[ii] - 1]))
   cnt[x[ii] - 1] += 1
end

m.times do |i|
    puts ans[i]
end