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

def pad(n):

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





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

P, Y = [0 for _ in range(M)], [0 for _ in range(M)]

for i in range(M):

    P[i], Y[i] = list(map(int, input().split()))



data = [[P[i], Y[i], 1, i] for i in range(M)]

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

for di in data:

    print((pad(di[0]) + pad(di[2])))

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

def pad(n):

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





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

P, Y = [0 for _ in range(M)], [0 for _ in range(M)]

for i in range(M):

    P[i], Y[i] = list(map(int, input().split()))



data = [[P[i], Y[i], 1, i] for i in range(M)]

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()))
P, Y = [0 for _ in range(M)], [0 for _ in range(M)]
for i in range(M):
    P[i], Y[i] = list(map(int, input().split()))
data = [[P[i], Y[i], 1, i] for i in range(M)]
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
for di in data:
    print((pad(di[0]) + pad(di[2])))

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


N, M = list(map(int, input().split()))
P, Y = [0 for _ in range(M)], [0 for _ in range(M)]
for i in range(M):
    P[i], Y[i] = list(map(int, input().split()))
data = [[P[i], Y[i], 1, i] for i in range(M)]
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)))

+ans = [] -    print((pad(di[0]) + pad(di[2]))) +    ans.append(pad(di[0]) + pad(di[2])) +print(("\n".join(ans)))