# https://atcoder.jp/contests/abc113/tasks/abc113_c

City = Struct.new(:p, :y, :id)

N, M = gets.split.map(&:to_i)
cs = Array.new(M)
M.times do |i|
  cs[i] = City.new(*gets.split.map(&:to_i), nil)
end

cs
.group_by { |c| c.p }
.each do |_k, vs|
  vs
  .sort_by { |v| v.y }
  .each.with_index(1) do |v, i|
    v.id = format('%06d', v.p) + format('%06d', i)
  end
end

cs.each { |c| puts "#{c.id}" }
