function read()
    return io.read("*num")
end
n = read()
m = read()
a = {}
for i = 1, m do
    p = read()
    y = read()
    a[i] = {p = p, y = y, id = i}
end
table.sort(a, function(A, B)
                return A.y < B.y
            end)

a[1].c = 1
b = {}
for i = 2, m do
    if a[i].y > a[i - 1].y then
        a[i].c = a[i - 1].c + 1
    else
        a[i].c = a[i - 1].c
    end
end

for i = 1, m do
    b[a[i].id] = a[i]
end

for i = 1, m do
    str = string.format("%06d%06d", b[i].p, b[i].c)
    print(str)
end


