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 = []

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.append((sorted_y[l][0], s1 + s2))



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

for h in range(m):

    print((ans[h][1]))
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]))
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 = []
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.append((sorted_y[l][0], s1 + s2))
ans = sorted(inums, key=lambda x: x[0])
for h in range(m):
    print((ans[h][1]))

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]))

-inums = [] +inums = [0 for z in range(m)] -            inums.append((sorted_y[l][0], s1 + s2)) -ans = sorted(inums, key=lambda x: x[0]) +            inums[sorted_y[l][0]] = s1 + s2 -    print((ans[h][1])) +    print((inums[h]))