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

A=[[] for i in range(N)]



for i in range(M):

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

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



X=[0]*M

for i,d in enumerate(A):

  d.sort()

  for k,(y,j) in enumerate(d):

    X[j]=str(i+1).zfill(6)+str(k+1).zfill(6)

print(*X,sep='\n')

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

A=[[] for i in range(N)]

for i in range(M):

  a,b=list(map(int,input().split()))

  A[a-1].append((b,i))

ans=[0]*M

for i in range(N):

  d=sorted(A[i])

  n=len(d)

  for j in range(n):

    a,b=d[j]

    D=str(i+1)

    E=str(j+1)

    r=D.zfill(6)+E.zfill(6)

    ans[b]=r

for i in ans:

  print(i)
N, M = map(int, input().split())
A = [[] for i in range(N)]
for i in range(M):
    p, y = map(int, input().split())
    A[p - 1].append((y, i))
X = [0] * M
for i, d in enumerate(A):
    d.sort()
    for k, (y, j) in enumerate(d):
        X[j] = str(i + 1).zfill(6) + str(k + 1).zfill(6)
print(*X, sep="\n")

N, M = list(map(int, input().split()))
A = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    A[a - 1].append((b, i))
ans = [0] * M
for i in range(N):
    d = sorted(A[i])
    n = len(d)
    for j in range(n):
        a, b = d[j]
        D = str(i + 1)
        E = str(j + 1)
        r = D.zfill(6) + E.zfill(6)
        ans[b] = r
for i in ans:
    print(i)

-N, M = map(int, input().split()) +N, M = list(map(int, input().split())) -    p, y = map(int, input().split()) -    A[p - 1].append((y, i)) -X = [0] * M -for i, d in enumerate(A): -    d.sort() -    for k, (y, j) in enumerate(d): -        X[j] = str(i + 1).zfill(6) + str(k + 1).zfill(6) -print(*X, sep="\n") +    a, b = list(map(int, input().split())) +    A[a - 1].append((b, i)) +ans = [0] * M +for i in range(N): +    d = sorted(A[i]) +    n = len(d) +    for j in range(n): +        a, b = d[j] +        D = str(i + 1) +        E = str(j + 1) +        r = D.zfill(6) + E.zfill(6) +        ans[b] = r +for i in ans: +    print(i)