N,M = gets.split.map(&:to_i)

#prefs = [[pref, year],...]
prefs = []
M.times do
  prefs << gets.split.map(&:to_i)
end

prefs_sorted = prefs.sort

order = Hash.new

cur_pref = prefs_sorted[0][0]
cur_order = 1

prefs_sorted.each do |(pref,year)|
  if cur_pref == pref
    order[year] = cur_order
    cur_order += 1
  else
    order[year] = 1
    cur_order = 2
    cur_pref = pref
  end
end

prefs.each do |(pref,year)|
  str = "%#06d" % pref + "%#06d" % order[year]
  puts str
end
