n, m = gets.split.map(&:to_i)
p = []
y = []
pi = Hash.new{|h,k| h[k] = []}
m.times do
  pp, yy = gets.split.map(&:to_i)
  p << pp
  y << yy
  pi[pp] << yy
end

pi.keys.each do |k|
  pi[k].sort!
end

m.times do |i|
  pp = p[i]
  yy = y[i]
  o = pi[pp].find_index(yy) + 1
  puts "%06d%06d" % [pp, o]
end
