n, m = gets.split.map(&:to_i)
city = []
m.times do |i|
  city[i] = i, *gets.split.map(&:to_i)
end
city.sort! do |c1, c2|
  if c1[1] == c2[1]
    c1[2] <=> c2[2]
  else
    c1[1] <=> c2[1]
  end
end
pref = nil
idx = 1
city.each do |c|
  if c[1] != pref
    idx = 1
    pref = c[1]
  else
    idx += 1
  end
  c[3] = idx
end
city.sort! do |c1, c2|
  c1[0] <=> c2[0]
end
city.each do |c|
  printf "%06d%06d\n", c[1], c[3]
end
