from operator import itemgetter

 

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

P = [0] * M

Y = [0] * M

for i in range(M):

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

n = [i for i in range(M)]

 

P, Y, n = list(zip(*sorted(zip(P, Y, n), key=itemgetter(0, 1))))

 

count = 1

ans = []

ans.append(str(P[0]).zfill(6) + str(count).zfill(6))

 

for i in range(M - 1):

    if P[i + 1] == P[i]:

        count += 1

    else:

        count = 1

    ans.append(str(P[i + 1]).zfill(6) + str(count).zfill(6))

 

n, ans = list(zip(*sorted(zip(n, ans), key=itemgetter(0))))

 

for i in ans:

    print(i)
import sys

from operator import itemgetter



read = sys.stdin.read



N, M, *PY = list(map(int, read().split()))

P = PY[::2]

Y = PY[1::2]



P, Y, I = list(zip(*sorted(zip(P, Y, list(range(M))), key=itemgetter(0, 1))))

P = list(map(str, P))

answer = []

prev_p = ''

n = 0

for p, i in zip(P, I):

    if prev_p == p:

        n += 1

    else:

        prev_p = p

        n = 1

    answer.append((p.zfill(6) + str(n).zfill(6), i))



answer.sort(key=itemgetter(1))

answer = [i for i, _ in answer]

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

from operator import itemgetter

N, M = list(map(int, input().split()))
P = [0] * M
Y = [0] * M
for i in range(M):
    P[i], Y[i] = list(map(int, input().split()))
n = [i for i in range(M)]
P, Y, n = list(zip(*sorted(zip(P, Y, n), key=itemgetter(0, 1))))
count = 1
ans = []
ans.append(str(P[0]).zfill(6) + str(count).zfill(6))
for i in range(M - 1):
    if P[i + 1] == P[i]:
        count += 1
    else:
        count = 1
    ans.append(str(P[i + 1]).zfill(6) + str(count).zfill(6))
n, ans = list(zip(*sorted(zip(n, ans), key=itemgetter(0))))
for i in ans:
    print(i)

import sys
from operator import itemgetter

read = sys.stdin.read
N, M, *PY = list(map(int, read().split()))
P = PY[::2]
Y = PY[1::2]
P, Y, I = list(zip(*sorted(zip(P, Y, list(range(M))), key=itemgetter(0, 1))))
P = list(map(str, P))
answer = []
prev_p = ""
n = 0
for p, i in zip(P, I):
    if prev_p == p:
        n += 1
    else:
        prev_p = p
        n = 1
    answer.append((p.zfill(6) + str(n).zfill(6), i))
answer.sort(key=itemgetter(1))
answer = [i for i, _ in answer]
print(("\n".join(answer)))

+import sys -N, M = list(map(int, input().split())) -P = [0] * M -Y = [0] * M -for i in range(M): -    P[i], Y[i] = list(map(int, input().split())) -n = [i for i in range(M)] -P, Y, n = list(zip(*sorted(zip(P, Y, n), key=itemgetter(0, 1)))) -count = 1 -ans = [] -ans.append(str(P[0]).zfill(6) + str(count).zfill(6)) -for i in range(M - 1): -    if P[i + 1] == P[i]: -        count += 1 +read = sys.stdin.read +N, M, *PY = list(map(int, read().split())) +P = PY[::2] +Y = PY[1::2] +P, Y, I = list(zip(*sorted(zip(P, Y, list(range(M))), key=itemgetter(0, 1)))) +P = list(map(str, P)) +answer = [] +prev_p = "" +n = 0 +for p, i in zip(P, I): +    if prev_p == p: +        n += 1 -        count = 1 -    ans.append(str(P[i + 1]).zfill(6) + str(count).zfill(6)) -n, ans = list(zip(*sorted(zip(n, ans), key=itemgetter(0)))) -for i in ans: -    print(i) +        prev_p = p +        n = 1 +    answer.append((p.zfill(6) + str(n).zfill(6), i)) +answer.sort(key=itemgetter(1)) +answer = [i for i, _ in answer] +print(("\n".join(answer)))