n,m=gets.chomp.split(" ").map(&:to_i)
#p_arrに県piが現状幾つの市があるか入れる
p_arr= Array.new(n,0)
p_y = Array.new(m)
for i in 0..m-1 do
  p_y[i]=gets.chomp.split(" ").map(&:to_i)
  p_y[i].push(i)
end
#市をできた順番に並べる
p_y.sort!{ |a, b| a[1] <=> b[1] }
for i in 0..m-1 do
  p_arr[p_y[i][0]-1]+=1
  p_y[i].push(p_arr[p_y[i][0]-1])
end
#市を入力順に並べる
p_y.sort!{ |a, b| a[2] <=> b[2] }
for i in 0..m-1 do
  printf("%06d",p_y[i][0])
  printf("%06d",p_y[i][3])
  puts ""
end