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

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

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

B={}

for x,y in A:

    if y[0] not in B:

        B[y[0]]=1

        y[1]=1

    else:

        B[y[0]] +=1

        y[1]=B[y[0]]



for i in sorted(A,key=lambda x:x[0]):

    print((str(i[1][0]).zfill(6)+str(i[1][1]).zfill(6)))
n,m=list(map(int,input().split()))

PY=sorted([list(map(int,input().split()))+[_] for _ in range(m)],key=lambda x:x[1])



A,B={},[]

for p,y,num in PY:

    if p not in A:

        A[p]=1

        B.append([p,A[p],num])

    else:

        A[p] +=1

        B.append([p,A[p],num])



for a,b,c in sorted(B,key=lambda x:x[2]):

    print((str(a).zfill(6)+str(b).zfill(6)))
n, m = list(map(int, input().split()))
A = [[i, list(map(int, input().split()))] for i in range(m)]
A.sort(key=lambda x: x[1][1])
B = {}
for x, y in A:
    if y[0] not in B:
        B[y[0]] = 1
        y[1] = 1
    else:
        B[y[0]] += 1
        y[1] = B[y[0]]
for i in sorted(A, key=lambda x: x[0]):
    print((str(i[1][0]).zfill(6) + str(i[1][1]).zfill(6)))

n, m = list(map(int, input().split()))
PY = sorted(
    [list(map(int, input().split())) + [_] for _ in range(m)], key=lambda x: x[1]
)
A, B = {}, []
for p, y, num in PY:
    if p not in A:
        A[p] = 1
        B.append([p, A[p], num])
    else:
        A[p] += 1
        B.append([p, A[p], num])
for a, b, c in sorted(B, key=lambda x: x[2]):
    print((str(a).zfill(6) + str(b).zfill(6)))

-A = [[i, list(map(int, input().split()))] for i in range(m)] -A.sort(key=lambda x: x[1][1]) -B = {} -for x, y in A: -    if y[0] not in B: -        B[y[0]] = 1 -        y[1] = 1 +PY = sorted( +    [list(map(int, input().split())) + [_] for _ in range(m)], key=lambda x: x[1] +) +A, B = {}, [] +for p, y, num in PY: +    if p not in A: +        A[p] = 1 +        B.append([p, A[p], num]) -        B[y[0]] += 1 -        y[1] = B[y[0]] -for i in sorted(A, key=lambda x: x[0]): -    print((str(i[1][0]).zfill(6) + str(i[1][1]).zfill(6))) +        A[p] += 1 +        B.append([p, A[p], num]) +for a, b, c in sorted(B, key=lambda x: x[2]): +    print((str(a).zfill(6) + str(b).zfill(6)))