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

ipy = []



for i in range(m):

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

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



ipy.sort(key=lambda x:x[2])

count = {}

order = {}



for i in range(m):

    i, p, y = ipy[i]

    if not p in count:

        count[p] = 0

    count[p] += 1

    order[i, p] = count[p]

    

ipy.sort(key=lambda x: x[0])

    

for i, p, y in ipy:

    print(('{:06}{:06}'.format(p, order[i, p])))
n, m = list(map(int, input().split()))

ipy = []



for i in range(m):

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

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



counter = {}

order = {}



for i, p, y in sorted(ipy, key = lambda x: x[2]):

    counter[p] = counter.get(p, 0) + 1

    order[i, p] = counter[p]

    

for i, p, y in ipy:

    print(('{:06}{:06}'.format(p, order[i, p])))
n, m = list(map(int, input().split()))
ipy = []
for i in range(m):
    p, y = list(map(int, input().split()))
    ipy.append([i, p, y])
ipy.sort(key=lambda x: x[2])
count = {}
order = {}
for i in range(m):
    i, p, y = ipy[i]
    if not p in count:
        count[p] = 0
    count[p] += 1
    order[i, p] = count[p]
ipy.sort(key=lambda x: x[0])
for i, p, y in ipy:
    print(("{:06}{:06}".format(p, order[i, p])))

n, m = list(map(int, input().split()))
ipy = []
for i in range(m):
    p, y = list(map(int, input().split()))
    ipy.append([i, p, y])
counter = {}
order = {}
for i, p, y in sorted(ipy, key=lambda x: x[2]):
    counter[p] = counter.get(p, 0) + 1
    order[i, p] = counter[p]
for i, p, y in ipy:
    print(("{:06}{:06}".format(p, order[i, p])))

-ipy.sort(key=lambda x: x[2]) -count = {} +counter = {} -for i in range(m): -    i, p, y = ipy[i] -    if not p in count: -        count[p] = 0 -    count[p] += 1 -    order[i, p] = count[p] -ipy.sort(key=lambda x: x[0]) +for i, p, y in sorted(ipy, key=lambda x: x[2]): +    counter[p] = counter.get(p, 0) + 1 +    order[i, p] = counter[p]