#!/usr/bin/env ruby
n, m = STDIN.readline.strip.split(' ').map(&:to_i)
py = STDIN.read.split("\n").map{|s| s.split(' ').map(&:to_i)}
def zero_p(i)
  i.to_s.rjust(6, '0')
end
p = []
py.each_with_index do |py, i|
  p[py[0]] = p[py[0]].nil? ? [[py[1], i]] : p[py[0]] + [[py[1], i]]
end
# puts "py:#{py}"
p.each do |pl|
  pl.sort!{|a, b| a[0]<=>b[0]} if pl
end
# puts "p:#{p}"
s = []
p.each_with_index do |pl, pi|
  next if pl.nil?
  pl.each_with_index do |pls, yi|
    _, ni = pls
    s[ni] = zero_p(pi) + zero_p(yi+1)
  end
end
# puts "s:#{p}"
s.each do |l|
  puts l
end

