Y_MASK = 10**10

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

PYs = (1..M).map{|i| STDIN.gets.chomp.split(" ").map(&:to_i)}

table = PYs.each_with_index.map{|py, i| [i, py]}.group_by{|e| e[1][0]}.each_value{|v| v.sort!{|a, b| a[1][1] <=> b[1][1]}}.each_value{|v| v.each_with_index{|e, i| e.push(sprintf("%06d%06d", e[1][0], i + 1))}}

puts table.values.flatten(1).sort{|a, b| a[0] <=> b[0]}.map{|e| e[2]}.join("\n")
