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

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



convertedPY = [

    {'index': i,

     'city': py[0],

     'year': py[1]

     } for i, py in enumerate(PY)

]

'''

3 4

1 32

3 64

3 63

1 33



'''

convertedPY = sorted(convertedPY, key=lambda a: (a['city'], a['year']))

answer = []

cnt = 0

tmp = convertedPY[0]['city']

#print(convertedPY)

result = []

for py in convertedPY:

    #print(tmp)

    temp_dict = {}

    if tmp == py['city']:

        cnt += 1

        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)

        temp_dict['index'] = py['index']

        result.append(temp_dict)

    else:

        cnt = 1

        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)

        temp_dict['index'] = py['index']

        result.append(temp_dict)

        tmp = py['city']





result = sorted(result, key=lambda a: a['index'])

#print(result)

for r in result:

    print((r['answer']))



'''

3

21 -11

81234 52141 94124

'''



#print(PY)

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

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



PY_sorted = sorted(PY, key=lambda a: (a[0], a[1]))

PY_sorted[0][3] = str(PY_sorted[0][0]).zfill(6) + str(1).zfill(6)

#print(PY_sorted)

cnt = 1

for i in range(1, M):

    cnt += 1

    if PY_sorted[i][0] != PY_sorted[i - 1][0]:

        cnt = 1

        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)

    else:

        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)

#print(PY_sorted)

ans = sorted(PY_sorted, key=lambda a: a[2])

for a in ans:

    print((a[3]))



N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) for i in range(M)]
convertedPY = [{"index": i, "city": py[0], "year": py[1]} for i, py in enumerate(PY)]
"""
3 4
1 32
3 64
3 63
1 33
"""
convertedPY = sorted(convertedPY, key=lambda a: (a["city"], a["year"]))
answer = []
cnt = 0
tmp = convertedPY[0]["city"]
# print(convertedPY)
result = []
for py in convertedPY:
    # print(tmp)
    temp_dict = {}
    if tmp == py["city"]:
        cnt += 1
        temp_dict["answer"] = "{:0=6}".format(py["city"]) + "{:0=6}".format(cnt)
        temp_dict["index"] = py["index"]
        result.append(temp_dict)
    else:
        cnt = 1
        temp_dict["answer"] = "{:0=6}".format(py["city"]) + "{:0=6}".format(cnt)
        temp_dict["index"] = py["index"]
        result.append(temp_dict)
        tmp = py["city"]
result = sorted(result, key=lambda a: a["index"])
# print(result)
for r in result:
    print((r["answer"]))
"""
3
21 -11
81234 52141 94124
"""
# print(PY)

N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i] + [0] for i in range(M)]
PY_sorted = sorted(PY, key=lambda a: (a[0], a[1]))
PY_sorted[0][3] = str(PY_sorted[0][0]).zfill(6) + str(1).zfill(6)
# print(PY_sorted)
cnt = 1
for i in range(1, M):
    cnt += 1
    if PY_sorted[i][0] != PY_sorted[i - 1][0]:
        cnt = 1
        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)
    else:
        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)
# print(PY_sorted)
ans = sorted(PY_sorted, key=lambda a: a[2])
for a in ans:
    print((a[3]))

-PY = [list(map(int, input().split())) for i in range(M)] -convertedPY = [{"index": i, "city": py[0], "year": py[1]} for i, py in enumerate(PY)] -""" -3 4 -1 32 -3 64 -3 63 -1 33 -""" -convertedPY = sorted(convertedPY, key=lambda a: (a["city"], a["year"])) -answer = [] -cnt = 0 -tmp = convertedPY[0]["city"] -# print(convertedPY) -result = [] -for py in convertedPY: -    # print(tmp) -    temp_dict = {} -    if tmp == py["city"]: -        cnt += 1 -        temp_dict["answer"] = "{:0=6}".format(py["city"]) + "{:0=6}".format(cnt) -        temp_dict["index"] = py["index"] -        result.append(temp_dict) +PY = [list(map(int, input().split())) + [i] + [0] for i in range(M)] +PY_sorted = sorted(PY, key=lambda a: (a[0], a[1])) +PY_sorted[0][3] = str(PY_sorted[0][0]).zfill(6) + str(1).zfill(6) +# print(PY_sorted) +cnt = 1 +for i in range(1, M): +    cnt += 1 +    if PY_sorted[i][0] != PY_sorted[i - 1][0]: +        cnt = 1 +        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6) -        cnt = 1 -        temp_dict["answer"] = "{:0=6}".format(py["city"]) + "{:0=6}".format(cnt) -        temp_dict["index"] = py["index"] -        result.append(temp_dict) -        tmp = py["city"] -result = sorted(result, key=lambda a: a["index"]) -# print(result) -for r in result: -    print((r["answer"])) -""" -3 -21 -11 -81234 52141 94124 -""" -# print(PY) +        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6) +# print(PY_sorted) +ans = sorted(PY_sorted, key=lambda a: a[2]) +for a in ans: +    print((a[3]))