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

P = [list(map(int, input().split())) for _ in range(M)]

cnt = (N+1)*[0]

ids = {}



for p,y in sorted(P,key=lambda x: x[1]):

	cnt[p] += 1

	ids[y] = "%06d%06d" % (p,cnt[p])



for _,y in P:

	print((ids[y]))
N,M = list(map(int, input().split()))

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

C = (N+1)*[0]

D = {}



for p,y in sorted(P,key=lambda x: x[1]):

  C[p]+= 1

  D[y]="%06d%06d" % (p,C[p])



for p,y in P:

  print((D[y]))
N, M = list(map(int, input().split()))
P = [list(map(int, input().split())) for _ in range(M)]
cnt = (N + 1) * [0]
ids = {}
for p, y in sorted(P, key=lambda x: x[1]):
    cnt[p] += 1
    ids[y] = "%06d%06d" % (p, cnt[p])
for _, y in P:
    print((ids[y]))

N, M = list(map(int, input().split()))
P = [list(map(int, input().split())) for m in range(M)]
C = (N + 1) * [0]
D = {}
for p, y in sorted(P, key=lambda x: x[1]):
    C[p] += 1
    D[y] = "%06d%06d" % (p, C[p])
for p, y in P:
    print((D[y]))

-P = [list(map(int, input().split())) for _ in range(M)] -cnt = (N + 1) * [0] -ids = {} +P = [list(map(int, input().split())) for m in range(M)] +C = (N + 1) * [0] +D = {} -    cnt[p] += 1 -    ids[y] = "%06d%06d" % (p, cnt[p]) -for _, y in P: -    print((ids[y])) +    C[p] += 1 +    D[y] = "%06d%06d" % (p, C[p]) +for p, y in P: +    print((D[y]))