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

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

prefs_sorted = prefs.sort

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

prefs_sorted.each_with_index do |(pref,year), i|
  if cur_pref == pref
    prefs_sorted[i] << cur_order
    cur_order += 1
  else
    prefs_sorted[i] << 1
    cur_order = 2
    cure_pref = pref
  end
end

prefs.each do |(pref,year)|
  order = -1
  prefs_sorted.each do |(p, y, o)|
    if pref == p && year == y
      order = o
      break
    end
  end
  str = "%#06d" % pref + "%#06d" % order
  puts str
end
