n,m = gets.split.map(&:to_i)
d = m.times.map{gets.split.map(&:to_i)}
m.times do |i|
    d[i] << i
end
d.sort_by!{|i,j,k|j}
a = Hash.new(0)
m.times do |i|
    a[d[i][0]] += 1
    d[i] << a[d[i][0]]
end
d.sort_by!{|i,j,k,l|k}
m.times do |i|
    puts ("00000"+(d[i][0].to_s))[-6..-1]+("00000"+(d[i][3].to_s))[-6..-1]
end