a,b = list(map(int,input().split()))

li = []

for i in range(b):

    li.append(input().split())

for i in range(b):

    li[i] = [int(x) for x in li[i]]

    li[i].append(i+1)

li.sort()

L = []

for i in range(a):

    L.append([])

for i in range(b):

    L[li[i][0]-1].append((li[i][0],li[i][1],li[i][2]))

ans = []

for i in range(a):

    for j in range(len(L[i])):

        ans.append((L[i][j][0],j+1,L[i][j][2]))

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

for i in range(b):

    print((str(ans[i][0]).zfill(6)+str(ans[i][1]).zfill(6)))
n,m = list(map(int,input().split()))

L = []

for i in range(m):

    li = list(map(int,input().split()))

    L.append(li)



li = []

for i,j in enumerate(L):

    li.append(j+[i])

li.sort(key = lambda x:(x[0],x[1]))



li.append([0,0,0])



k,r = li[0][0],1

for i in range(m):

    if li[i][0] == k:

        if li[i+1][1] == li[i][1]:

            li[i][1] = r

            li[i+1][1] = r

        else:

            li[i][1] = r

            r +=1

    else:

        k = li[i][0]

        r = 1

        li[i][1] = r

        r +=1



li.pop()



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



for i in range(m):

    print(("{:06d}".format(li[i][0])+"{:06d}".format(li[i][1])))
a, b = list(map(int, input().split()))
li = []
for i in range(b):
    li.append(input().split())
for i in range(b):
    li[i] = [int(x) for x in li[i]]
    li[i].append(i + 1)
li.sort()
L = []
for i in range(a):
    L.append([])
for i in range(b):
    L[li[i][0] - 1].append((li[i][0], li[i][1], li[i][2]))
ans = []
for i in range(a):
    for j in range(len(L[i])):
        ans.append((L[i][j][0], j + 1, L[i][j][2]))
ans.sort(key=lambda x: x[2])
for i in range(b):
    print((str(ans[i][0]).zfill(6) + str(ans[i][1]).zfill(6)))

n, m = list(map(int, input().split()))
L = []
for i in range(m):
    li = list(map(int, input().split()))
    L.append(li)
li = []
for i, j in enumerate(L):
    li.append(j + [i])
li.sort(key=lambda x: (x[0], x[1]))
li.append([0, 0, 0])
k, r = li[0][0], 1
for i in range(m):
    if li[i][0] == k:
        if li[i + 1][1] == li[i][1]:
            li[i][1] = r
            li[i + 1][1] = r
        else:
            li[i][1] = r
            r += 1
    else:
        k = li[i][0]
        r = 1
        li[i][1] = r
        r += 1
li.pop()
li.sort(key=lambda x: x[2])
for i in range(m):
    print(("{:06d}".format(li[i][0]) + "{:06d}".format(li[i][1])))

-a, b = list(map(int, input().split())) +n, m = list(map(int, input().split())) +L = [] +for i in range(m): +    li = list(map(int, input().split())) +    L.append(li) -for i in range(b): -    li.append(input().split()) -for i in range(b): -    li[i] = [int(x) for x in li[i]] -    li[i].append(i + 1) -li.sort() -L = [] -for i in range(a): -    L.append([]) -for i in range(b): -    L[li[i][0] - 1].append((li[i][0], li[i][1], li[i][2])) -ans = [] -for i in range(a): -    for j in range(len(L[i])): -        ans.append((L[i][j][0], j + 1, L[i][j][2])) -ans.sort(key=lambda x: x[2]) -for i in range(b): -    print((str(ans[i][0]).zfill(6) + str(ans[i][1]).zfill(6))) +for i, j in enumerate(L): +    li.append(j + [i]) +li.sort(key=lambda x: (x[0], x[1])) +li.append([0, 0, 0]) +k, r = li[0][0], 1 +for i in range(m): +    if li[i][0] == k: +        if li[i + 1][1] == li[i][1]: +            li[i][1] = r +            li[i + 1][1] = r +        else: +            li[i][1] = r +            r += 1 +    else: +        k = li[i][0] +        r = 1 +        li[i][1] = r +        r += 1 +li.pop() +li.sort(key=lambda x: x[2]) +for i in range(m): +    print(("{:06d}".format(li[i][0]) + "{:06d}".format(li[i][1])))