# https://abc113.contest.atcoder.jp/tasks/abc113_c

def pad(n):

    return '{:0>6}'.format(n)





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

data = [None for _ in range(M)]

for i in range(M):

    Pi, Yi = list(map(int, input().split()))

    data[i] = [Pi, Yi, 1, i]



data.sort(key=lambda x: x[1])  # sort by year

data.sort(key=lambda x: x[0])  # sort by prefectures



for i in range(1, M):

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

        data[i][2] = data[i - 1][2] + 1



data.sort(key=lambda x: x[-1])  # original order

ans = []

for di in data:

    ans.append(pad(di[0]) + pad(di[2]))

print(('\n'.join(ans)))

# https://abc113.contest.atcoder.jp/tasks/abc113_c

def pad(n):

    return '{:0>6}'.format(n)





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

work = [None for _ in range(M)]

orig = [None for _ in range(M)]  # retains original order

for i in range(M):

    Pi, Yi = list(map(int, input().split()))

    data = [Pi, Yi, 1, i]

    work[i] = data

    orig[i] = data



work.sort(key=lambda x: x[1])  # sort by year

work.sort(key=lambda x: x[0])  # sort by prefectures



for i in range(1, M):

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

        work[i][2] = work[i - 1][2] + 1



ans = []

for di in orig:

    ans.append(pad(di[0]) + pad(di[2]))

print(('\n'.join(ans)))

# https://abc113.contest.atcoder.jp/tasks/abc113_c
def pad(n):
    return "{:0>6}".format(n)


N, M = list(map(int, input().split()))
data = [None for _ in range(M)]
for i in range(M):
    Pi, Yi = list(map(int, input().split()))
    data[i] = [Pi, Yi, 1, i]
data.sort(key=lambda x: x[1])  # sort by year
data.sort(key=lambda x: x[0])  # sort by prefectures
for i in range(1, M):
    if data[i][0] == data[i - 1][0]:
        data[i][2] = data[i - 1][2] + 1
data.sort(key=lambda x: x[-1])  # original order
ans = []
for di in data:
    ans.append(pad(di[0]) + pad(di[2]))
print(("\n".join(ans)))

# https://abc113.contest.atcoder.jp/tasks/abc113_c
def pad(n):
    return "{:0>6}".format(n)


N, M = list(map(int, input().split()))
work = [None for _ in range(M)]
orig = [None for _ in range(M)]  # retains original order
for i in range(M):
    Pi, Yi = list(map(int, input().split()))
    data = [Pi, Yi, 1, i]
    work[i] = data
    orig[i] = data
work.sort(key=lambda x: x[1])  # sort by year
work.sort(key=lambda x: x[0])  # sort by prefectures
for i in range(1, M):
    if work[i][0] == work[i - 1][0]:
        work[i][2] = work[i - 1][2] + 1
ans = []
for di in orig:
    ans.append(pad(di[0]) + pad(di[2]))
print(("\n".join(ans)))

-data = [None for _ in range(M)] +work = [None for _ in range(M)] +orig = [None for _ in range(M)]  # retains original order -    data[i] = [Pi, Yi, 1, i] -data.sort(key=lambda x: x[1])  # sort by year -data.sort(key=lambda x: x[0])  # sort by prefectures +    data = [Pi, Yi, 1, i] +    work[i] = data +    orig[i] = data +work.sort(key=lambda x: x[1])  # sort by year +work.sort(key=lambda x: x[0])  # sort by prefectures -    if data[i][0] == data[i - 1][0]: -        data[i][2] = data[i - 1][2] + 1 -data.sort(key=lambda x: x[-1])  # original order +    if work[i][0] == work[i - 1][0]: +        work[i][2] = work[i - 1][2] + 1 -for di in data: +for di in orig: