N,M = map(int,input().split())

data = [[i,list(map(int,input().split()))] for i in range(M)]



# print(data)

sortdata = sorted(data, key=lambda data:data[1])

# print(sortdata)



cnt = 1

sortdata[0].append(1)

for i in range(1,M):

    if sortdata[i][1][0] == sortdata[i-1][1][0]:

        cnt += 1

    else:

        cnt = 1

    sortdata[i].append(cnt)



sortdata = sorted(sortdata, key=lambda data:data[0])

for i in range(M):

    print(str(sortdata[i][1][0]).rjust(6,'0'),end = "")

    print(str(sortdata[i][2]).rjust(6,'0'))

import sys

N,M = map(int,input().split())

data = [[i,list(map(int,sys.stdin.readline().rstrip().split()))] for i in range(M)]



# print(data)

sortdata = sorted(data, key=lambda data:data[1])

# print(sortdata)



cnt = 1

sortdata[0].append(1)

for i in range(1,M):

    if sortdata[i][1][0] == sortdata[i-1][1][0]:

        cnt += 1

    else:

        cnt = 1

    sortdata[i].append(cnt)



sortdata = sorted(sortdata, key=lambda data:data[0])

for i in range(M):

    print(str(sortdata[i][1][0]).rjust(6,'0'),end = "")

    print(str(sortdata[i][2]).rjust(6,'0'))

N, M = map(int, input().split())
data = [[i, list(map(int, input().split()))] for i in range(M)]
# print(data)
sortdata = sorted(data, key=lambda data: data[1])
# print(sortdata)
cnt = 1
sortdata[0].append(1)
for i in range(1, M):
    if sortdata[i][1][0] == sortdata[i - 1][1][0]:
        cnt += 1
    else:
        cnt = 1
    sortdata[i].append(cnt)
sortdata = sorted(sortdata, key=lambda data: data[0])
for i in range(M):
    print(str(sortdata[i][1][0]).rjust(6, "0"), end="")
    print(str(sortdata[i][2]).rjust(6, "0"))

import sys

N, M = map(int, input().split())
data = [[i, list(map(int, sys.stdin.readline().rstrip().split()))] for i in range(M)]
# print(data)
sortdata = sorted(data, key=lambda data: data[1])
# print(sortdata)
cnt = 1
sortdata[0].append(1)
for i in range(1, M):
    if sortdata[i][1][0] == sortdata[i - 1][1][0]:
        cnt += 1
    else:
        cnt = 1
    sortdata[i].append(cnt)
sortdata = sorted(sortdata, key=lambda data: data[0])
for i in range(M):
    print(str(sortdata[i][1][0]).rjust(6, "0"), end="")
    print(str(sortdata[i][2]).rjust(6, "0"))

+import sys + -data = [[i, list(map(int, input().split()))] for i in range(M)] +data = [[i, list(map(int, sys.stdin.readline().rstrip().split()))] for i in range(M)]