

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

#A=[]

Y=[[] for _ in range(N)] #県

for i in range(M):

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

  #A.append((p,y))

  Y[p-1].append([y,i+1])



for i in range(N):

  if Y[i]:

    Y[i].sort(key=lambda x: x[0])

#indexは時間かかる

ans=[]

for i in range(N):

  for j,L in enumerate(Y[i]):

    p,y,n=i+1, L[0],L[1]

    ans.append((n,p,j+1))

ans=sorted(ans)

for n,p,y in ans:

  a=(6-len(str(p)))*"0"+str(p)+(6-len(str(y)))*"0"+str(y)

  print(a)
import bisect

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

P=[[] for _ in range(N)]

L=[]

for i in range(M):

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

    L.append((p,y))

    P[p-1].append(y)



newP=[]

for p in P:

    p=sorted(p)

    newP.append(p)



for i in range(M):

    t=L[i]

    p,y=t

    num=bisect.bisect_right(newP[p-1],y)

    

    p=str(p).zfill(6)

    num=str(num).zfill(6)

    print((p+num))

N, M = list(map(int, input().split()))
# A=[]
Y = [[] for _ in range(N)]  # 県
for i in range(M):
    p, y = list(map(int, input().split()))
    # A.append((p,y))
    Y[p - 1].append([y, i + 1])
for i in range(N):
    if Y[i]:
        Y[i].sort(key=lambda x: x[0])
# indexは時間かかる
ans = []
for i in range(N):
    for j, L in enumerate(Y[i]):
        p, y, n = i + 1, L[0], L[1]
        ans.append((n, p, j + 1))
ans = sorted(ans)
for n, p, y in ans:
    a = (6 - len(str(p))) * "0" + str(p) + (6 - len(str(y))) * "0" + str(y)
    print(a)

import bisect

N, M = list(map(int, input().split()))
P = [[] for _ in range(N)]
L = []
for i in range(M):
    p, y = list(map(int, input().split()))
    L.append((p, y))
    P[p - 1].append(y)
newP = []
for p in P:
    p = sorted(p)
    newP.append(p)
for i in range(M):
    t = L[i]
    p, y = t
    num = bisect.bisect_right(newP[p - 1], y)
    p = str(p).zfill(6)
    num = str(num).zfill(6)
    print((p + num))

+import bisect + -# A=[] -Y = [[] for _ in range(N)]  # 県 +P = [[] for _ in range(N)] +L = [] -    # A.append((p,y)) -    Y[p - 1].append([y, i + 1]) -for i in range(N): -    if Y[i]: -        Y[i].sort(key=lambda x: x[0]) -# indexは時間かかる -ans = [] -for i in range(N): -    for j, L in enumerate(Y[i]): -        p, y, n = i + 1, L[0], L[1] -        ans.append((n, p, j + 1)) -ans = sorted(ans) -for n, p, y in ans: -    a = (6 - len(str(p))) * "0" + str(p) + (6 - len(str(y))) * "0" + str(y) -    print(a) +    L.append((p, y)) +    P[p - 1].append(y) +newP = [] +for p in P: +    p = sorted(p) +    newP.append(p) +for i in range(M): +    t = L[i] +    p, y = t +    num = bisect.bisect_right(newP[p - 1], y) +    p = str(p).zfill(6) +    num = str(num).zfill(6) +    print((p + num))