from operator import itemgetter

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



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



b=[[i] for i in range(m)]



for i in range(m):

  p[i].extend(b[i])

  

p = sorted(sorted(p, key=itemgetter(1)))



old_p=0

for i in range(m):

  if p[i][0] != old_p :

    old_p = p[i][0]

    count = 1

  else:

    count +=1

  p[i][0] = "0"*(6-len(str(p[i][0])))+str(p[i][0])+"0"*(6-len(str(count)))+str(count)



p = sorted(p, key=itemgetter(2))



for i in range(m):

  print((p[i][0]))

  
from operator import itemgetter





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

info = [list(map(int, input().split())) + [i] for i in range(m)]



info = sorted(info, key=itemgetter(1))

ans = [0] * m



cnt_ind = [1] * (n + 1)

for i in range(m):

    p, y, ind = info[i]

    cnt = cnt_ind[p]

    cnt_ind[p] += 1

    ans[ind] = ("0000000"+str(p))[-6:] + ("0000000"+str(cnt))[-6:]

for i in ans:

    print(i)
from operator import itemgetter

n, m = list(map(int, input().split()))
p = [list(map(int, input().split())) for i in range(m)]
b = [[i] for i in range(m)]
for i in range(m):
    p[i].extend(b[i])
p = sorted(sorted(p, key=itemgetter(1)))
old_p = 0
for i in range(m):
    if p[i][0] != old_p:
        old_p = p[i][0]
        count = 1
    else:
        count += 1
    p[i][0] = (
        "0" * (6 - len(str(p[i][0])))
        + str(p[i][0])
        + "0" * (6 - len(str(count)))
        + str(count)
    )
p = sorted(p, key=itemgetter(2))
for i in range(m):
    print((p[i][0]))

from operator import itemgetter

n, m = list(map(int, input().split()))
info = [list(map(int, input().split())) + [i] for i in range(m)]
info = sorted(info, key=itemgetter(1))
ans = [0] * m
cnt_ind = [1] * (n + 1)
for i in range(m):
    p, y, ind = info[i]
    cnt = cnt_ind[p]
    cnt_ind[p] += 1
    ans[ind] = ("0000000" + str(p))[-6:] + ("0000000" + str(cnt))[-6:]
for i in ans:
    print(i)

-p = [list(map(int, input().split())) for i in range(m)] -b = [[i] for i in range(m)] +info = [list(map(int, input().split())) + [i] for i in range(m)] +info = sorted(info, key=itemgetter(1)) +ans = [0] * m +cnt_ind = [1] * (n + 1) -    p[i].extend(b[i]) -p = sorted(sorted(p, key=itemgetter(1))) -old_p = 0 -for i in range(m): -    if p[i][0] != old_p: -        old_p = p[i][0] -        count = 1 -    else: -        count += 1 -    p[i][0] = ( -        "0" * (6 - len(str(p[i][0]))) -        + str(p[i][0]) -        + "0" * (6 - len(str(count))) -        + str(count) -    ) -p = sorted(p, key=itemgetter(2)) -for i in range(m): -    print((p[i][0])) +    p, y, ind = info[i] +    cnt = cnt_ind[p] +    cnt_ind[p] += 1 +    ans[ind] = ("0000000" + str(p))[-6:] + ("0000000" + str(cnt))[-6:] +for i in ans: +    print(i)