n, m = list(map(int, input().split()))



city = []

for i in range(m):

    p, y = list(map(int, input().split()))

    city.append([i + 1, p, y])

city = sorted(city, key=lambda x: [x[1], x[2]])



res = []

p, pp = 0, 0

cnt = 0

for i in range(m):

    idx, p, _ = city[i]

    if i == 0:

        cnt = 1

        pp = p

    elif pp == p:

        cnt += 1

    else:

        pp = p

        cnt = 1



    ID = str(p).rjust(6, '0') + str(cnt).rjust(6, '0')

    res.append([idx, ID])



res = sorted(res, key=lambda x: x[0])

for i in res:

    print((i[1]))

import sys



sys.setrecursionlimit(10 ** 7)

f_inf = float('inf')

mod = 10 ** 9 + 7





def resolve():

    n, m = list(map(int, input().split()))

    PY = []

    for i in range(m):

        p, y = list(map(int, input().split()))

        PY.append([i, p, y])

    PY = sorted(PY, key=lambda x: x[2])

    PY = sorted(PY, key=lambda x: x[1])



    res = [] * m

    prev = PY[0][1]

    last = 0

    for i in range(m):

        idx, p, y = PY[i]

        if prev != p:

            last = 1

            prev = p

        else:

            last += 1



        id = str(p).zfill(6) + str(last).zfill(6)

        res.append([idx, id])



    res = sorted(res, key=lambda x: x[0])

    for i in res:

        print((i[1]))





if __name__ == '__main__':

    resolve()

n, m = list(map(int, input().split()))
city = []
for i in range(m):
    p, y = list(map(int, input().split()))
    city.append([i + 1, p, y])
city = sorted(city, key=lambda x: [x[1], x[2]])
res = []
p, pp = 0, 0
cnt = 0
for i in range(m):
    idx, p, _ = city[i]
    if i == 0:
        cnt = 1
        pp = p
    elif pp == p:
        cnt += 1
    else:
        pp = p
        cnt = 1
    ID = str(p).rjust(6, "0") + str(cnt).rjust(6, "0")
    res.append([idx, ID])
res = sorted(res, key=lambda x: x[0])
for i in res:
    print((i[1]))

import sys

sys.setrecursionlimit(10**7)
f_inf = float("inf")
mod = 10**9 + 7


def resolve():
    n, m = list(map(int, input().split()))
    PY = []
    for i in range(m):
        p, y = list(map(int, input().split()))
        PY.append([i, p, y])
    PY = sorted(PY, key=lambda x: x[2])
    PY = sorted(PY, key=lambda x: x[1])
    res = [] * m
    prev = PY[0][1]
    last = 0
    for i in range(m):
        idx, p, y = PY[i]
        if prev != p:
            last = 1
            prev = p
        else:
            last += 1
        id = str(p).zfill(6) + str(last).zfill(6)
        res.append([idx, id])
    res = sorted(res, key=lambda x: x[0])
    for i in res:
        print((i[1]))


if __name__ == "__main__":
    resolve()

-n, m = list(map(int, input().split())) -city = [] -for i in range(m): -    p, y = list(map(int, input().split())) -    city.append([i + 1, p, y]) -city = sorted(city, key=lambda x: [x[1], x[2]]) -res = [] -p, pp = 0, 0 -cnt = 0 -for i in range(m): -    idx, p, _ = city[i] -    if i == 0: -        cnt = 1 -        pp = p -    elif pp == p: -        cnt += 1 -    else: -        pp = p -        cnt = 1 -    ID = str(p).rjust(6, "0") + str(cnt).rjust(6, "0") -    res.append([idx, ID]) -res = sorted(res, key=lambda x: x[0]) -for i in res: -    print((i[1])) +import sys + +sys.setrecursionlimit(10**7) +f_inf = float("inf") +mod = 10**9 + 7 + + +def resolve(): +    n, m = list(map(int, input().split())) +    PY = [] +    for i in range(m): +        p, y = list(map(int, input().split())) +        PY.append([i, p, y]) +    PY = sorted(PY, key=lambda x: x[2]) +    PY = sorted(PY, key=lambda x: x[1]) +    res = [] * m +    prev = PY[0][1] +    last = 0 +    for i in range(m): +        idx, p, y = PY[i] +        if prev != p: +            last = 1 +            prev = p +        else: +            last += 1 +        id = str(p).zfill(6) + str(last).zfill(6) +        res.append([idx, id]) +    res = sorted(res, key=lambda x: x[0]) +    for i in res: +        print((i[1])) + + +if __name__ == "__main__": +    resolve()