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

A = []

B = []

for i in range(M):

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

    A.append([p, y, i])

A.sort()



cur = 1

cnt = 1

for i in range(M):

    if A[i][0] == cur:

        A[i].append(cnt)

        cnt += 1

    else:

        cur = A[i][0]

        cnt = 1

        A[i].append(cnt)

        cnt += 1

A.sort(key=lambda x: x[2])



for a in A:

    print(("%06d%06d" % (a[0], a[3])))
from collections import defaultdict

from bisect import bisect_left



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

A = []

B = defaultdict(list)



for i in range(M):

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

    A.append([p, y])

    B[p].append(y)



for key in list(B.keys()):

    B[key].sort()



for a in A:

    print(("%06d%06d" % (a[0], bisect_left(B[a[0]], a[1])+1)))
N, M = list(map(int, input().split()))
A = []
B = []
for i in range(M):
    p, y = list(map(int, input().split()))
    A.append([p, y, i])
A.sort()
cur = 1
cnt = 1
for i in range(M):
    if A[i][0] == cur:
        A[i].append(cnt)
        cnt += 1
    else:
        cur = A[i][0]
        cnt = 1
        A[i].append(cnt)
        cnt += 1
A.sort(key=lambda x: x[2])
for a in A:
    print(("%06d%06d" % (a[0], a[3])))

from collections import defaultdict
from bisect import bisect_left

N, M = list(map(int, input().split()))
A = []
B = defaultdict(list)
for i in range(M):
    p, y = list(map(int, input().split()))
    A.append([p, y])
    B[p].append(y)
for key in list(B.keys()):
    B[key].sort()
for a in A:
    print(("%06d%06d" % (a[0], bisect_left(B[a[0]], a[1]) + 1)))

+from collections import defaultdict +from bisect import bisect_left + -B = [] +B = defaultdict(list) -    A.append([p, y, i]) -A.sort() -cur = 1 -cnt = 1 -for i in range(M): -    if A[i][0] == cur: -        A[i].append(cnt) -        cnt += 1 -    else: -        cur = A[i][0] -        cnt = 1 -        A[i].append(cnt) -        cnt += 1 -A.sort(key=lambda x: x[2]) +    A.append([p, y]) +    B[p].append(y) +for key in list(B.keys()): +    B[key].sort() -    print(("%06d%06d" % (a[0], a[3]))) +    print(("%06d%06d" % (a[0], bisect_left(B[a[0]], a[1]) + 1)))