def solve(n, m, data)
  data.group_by(&:first)
    .map { |k, v| [k, v.map!(&:last).sort!] }
    .flat_map do |p, years|
    pref = sprintf('%06d', p)
    years.map!.with_index {| _, i| "#{pref}#{sprintf('%06d', i + 1)}"}
  end
end

def main
  stdin = STDIN.gets
  nm = stdin.split(/\s/)
  n = nm[0].to_i
  m = nm[1].to_i

  data = []
  (0...m).each do
    stdin = STDIN.gets
    p_y = stdin.split(/\s/).map!(&:to_i)
    data.push(p_y)
  end

  ret = solve(n, m, data)
  ret.each { |r| puts r }
end

main