N,M = gets.split.map(&:to_i)
C = Array.new(M){gets.split.map(&:to_i)}

City = Struct.new(:p, :y, :i, :j)
cities = C.map.with_index do |c, i|
    City.new(*c, i)
end

j = 0
pre = nil
cities.sort_by{|c| c.p * 10 ** 9 + c.y}.each do |c|
    if pre != c.p
        j = 0
    end

    j += 1
    pre = c.p
    c.j = j
end

cities.each do |c|
    printf("%06d%06d\n", c.p, c.j)
end
