import numpy as np

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

cities = {}

P = {}

Y = {}

for i in range(M):

    p,y = list(map(int, input().split()))

    cities[i] = p

    Y[i] = y



ans = {}

sorted_Y = sorted(list(Y.items()), key=lambda x:x[1])

P_i = np.zeros(N)

for i,y in sorted_Y:

    p = cities[i]

    P_i[p-1] += 1

    ans[i] = (p, int(P_i[p-1]))



for i in range(M):

    print(('{0:06}{1:06}'.format(ans[i][0], ans[i][1])))

"""

import numpy as np

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

cities = {}

Y = {}

for i in range(M):

    p,y = map(int, input().split())

    cities[i] = p

    Y[i] = y



ans = {}

sorted_Y = sorted(Y.items(), key=lambda x:x[1])

P_i = np.zeros(N)

for i,y in sorted_Y:

    p = cities[i]

    P_i[p-1] += 1

    ans[i] = (p, int(P_i[p-1]))



for i in range(M):

    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))

"""



n, m = list(map(int,input().split()))

pys = []

for i in range(m):

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

    x = [x[0],x[1],i]

    pys.append(x)



pys.sort()

pp = -1

lid = 0

ans = [0]*m

for i in range(m):

    if pp == pys[i][0]:

        lid += 1

    else:

        lid = 1

        pp = pys[i][0]

    ans[pys[i][2]] = pp*10**6+lid



for v in ans:

    print(('{:012d}'.format(v)))

import numpy as np

N, M = list(map(int, input().split()))
cities = {}
P = {}
Y = {}
for i in range(M):
    p, y = list(map(int, input().split()))
    cities[i] = p
    Y[i] = y
ans = {}
sorted_Y = sorted(list(Y.items()), key=lambda x: x[1])
P_i = np.zeros(N)
for i, y in sorted_Y:
    p = cities[i]
    P_i[p - 1] += 1
    ans[i] = (p, int(P_i[p - 1]))
for i in range(M):
    print(("{0:06}{1:06}".format(ans[i][0], ans[i][1])))

"""
import numpy as np
N, M = map(int, input().split())
cities = {}
Y = {}
for i in range(M):
    p,y = map(int, input().split())
    cities[i] = p
    Y[i] = y
ans = {}
sorted_Y = sorted(Y.items(), key=lambda x:x[1])
P_i = np.zeros(N)
for i,y in sorted_Y:
    p = cities[i]
    P_i[p-1] += 1
    ans[i] = (p, int(P_i[p-1]))
for i in range(M):
    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1]))
"""
n, m = list(map(int, input().split()))
pys = []
for i in range(m):
    x = list(map(int, input().split()))
    x = [x[0], x[1], i]
    pys.append(x)
pys.sort()
pp = -1
lid = 0
ans = [0] * m
for i in range(m):
    if pp == pys[i][0]:
        lid += 1
    else:
        lid = 1
        pp = pys[i][0]
    ans[pys[i][2]] = pp * 10**6 + lid
for v in ans:
    print(("{:012d}".format(v)))

+""" - -N, M = list(map(int, input().split())) +N, M = map(int, input().split()) -P = {} -    p, y = list(map(int, input().split())) +    p,y = map(int, input().split()) -sorted_Y = sorted(list(Y.items()), key=lambda x: x[1]) +sorted_Y = sorted(Y.items(), key=lambda x:x[1]) -for i, y in sorted_Y: +for i,y in sorted_Y: -    P_i[p - 1] += 1 -    ans[i] = (p, int(P_i[p - 1])) +    P_i[p-1] += 1 +    ans[i] = (p, int(P_i[p-1])) -    print(("{0:06}{1:06}".format(ans[i][0], ans[i][1]))) +    print('{0:06}{1:06}'.format(ans[i][0], ans[i][1])) +""" +n, m = list(map(int, input().split())) +pys = [] +for i in range(m): +    x = list(map(int, input().split())) +    x = [x[0], x[1], i] +    pys.append(x) +pys.sort() +pp = -1 +lid = 0 +ans = [0] * m +for i in range(m): +    if pp == pys[i][0]: +        lid += 1 +    else: +        lid = 1 +        pp = pys[i][0] +    ans[pys[i][2]] = pp * 10**6 + lid +for v in ans: +    print(("{:012d}".format(v)))