list1 = input().split()

n = int(list1[0])

m = int(list1[1])

pre = [[] for i in range(n)]



for j in range(m):

    data = input().split()

    p = int(data[0])

    y = int(data[1])

    pre[p - 1].append((j, y))



inums = [0 for z in range(m)]

for k in range(n):

    if len(pre[k]) == 0:

        pass

    else:

        sorted_y = sorted(pre[k], key = lambda x:x[1])

        for l in range(len(sorted_y)):

            s1 = str(k + 1).zfill(6)

            s2 = str(l + 1).zfill(6)

            inums[sorted_y[l][0]] = s1 + s2



for h in range(m):

    print((inums[h]))
n, m = map(int, input().split())

pre = [[] for i in range(n)]



for j in range(m):

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

    pre[p - 1].append((y, j))



inums = [0] * m

for k in range(n):

    if len(pre[k]) == 0:

        pass

    else:

        sorted_y = sorted(pre[k])

        for l in range(len(sorted_y)):

            s1 = str(k + 1).zfill(6)

            s2 = str(l + 1).zfill(6)

            inums[sorted_y[l][1]] = s1 + s2



print(*inums, sep = "\n")

list1 = input().split()
n = int(list1[0])
m = int(list1[1])
pre = [[] for i in range(n)]
for j in range(m):
    data = input().split()
    p = int(data[0])
    y = int(data[1])
    pre[p - 1].append((j, y))
inums = [0 for z in range(m)]
for k in range(n):
    if len(pre[k]) == 0:
        pass
    else:
        sorted_y = sorted(pre[k], key=lambda x: x[1])
        for l in range(len(sorted_y)):
            s1 = str(k + 1).zfill(6)
            s2 = str(l + 1).zfill(6)
            inums[sorted_y[l][0]] = s1 + s2
for h in range(m):
    print((inums[h]))

n, m = map(int, input().split())
pre = [[] for i in range(n)]
for j in range(m):
    p, y = map(int, input().split())
    pre[p - 1].append((y, j))
inums = [0] * m
for k in range(n):
    if len(pre[k]) == 0:
        pass
    else:
        sorted_y = sorted(pre[k])
        for l in range(len(sorted_y)):
            s1 = str(k + 1).zfill(6)
            s2 = str(l + 1).zfill(6)
            inums[sorted_y[l][1]] = s1 + s2
print(*inums, sep="\n")

-list1 = input().split() -n = int(list1[0]) -m = int(list1[1]) +n, m = map(int, input().split()) -    data = input().split() -    p = int(data[0]) -    y = int(data[1]) -    pre[p - 1].append((j, y)) -inums = [0 for z in range(m)] +    p, y = map(int, input().split()) +    pre[p - 1].append((y, j)) +inums = [0] * m -        sorted_y = sorted(pre[k], key=lambda x: x[1]) +        sorted_y = sorted(pre[k]) -            inums[sorted_y[l][0]] = s1 + s2 -for h in range(m): -    print((inums[h])) +            inums[sorted_y[l][1]] = s1 + s2 +print(*inums, sep="\n")