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

PY=[[0,0,0] for i in range(M)] 

for i in range(M):

  P,Y=list(map(int,input().split()))

  PY[i]=[P,Y,i]

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

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

prev=0

for i in range(M):

  if PY[i][0] != prev:

    count = 1

  else:

    count+=1

  prev=PY[i][0]

  ans=["0" for i in range(6 - len(str(prev)))]

  temp=["0" for i in range(6 - len(str(count)))]

  ans+=list(str(prev))+temp+list(str(count))

  PY[i][0]="".join(ans)

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

for i in range(M):

  print((PY[i][0]))
N, M = map(int, input().split())

PY = [tuple(list(map(int, input().split()))+[i]) for i in range(M)]

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

ans = ['']*M

P = [0]*N

for p, y, i in PY:

    ret = ''

    p -= 1

    P[p] += 1

    ret += '{:0=6}'.format(p+1)

    ret += '{:0=6}'.format(P[p])

    ans[i] = ret

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

N, M = list(map(int, input().split()))
PY = [[0, 0, 0] for i in range(M)]
for i in range(M):
    P, Y = list(map(int, input().split()))
    PY[i] = [P, Y, i]
PY.sort(key=lambda x: x[1])
PY.sort(key=lambda x: x[0])
prev = 0
for i in range(M):
    if PY[i][0] != prev:
        count = 1
    else:
        count += 1
    prev = PY[i][0]
    ans = ["0" for i in range(6 - len(str(prev)))]
    temp = ["0" for i in range(6 - len(str(count)))]
    ans += list(str(prev)) + temp + list(str(count))
    PY[i][0] = "".join(ans)
PY.sort(key=lambda x: x[2])
for i in range(M):
    print((PY[i][0]))

N, M = map(int, input().split())
PY = [tuple(list(map(int, input().split())) + [i]) for i in range(M)]
PY.sort(key=lambda x: x[1])
ans = [""] * M
P = [0] * N
for p, y, i in PY:
    ret = ""
    p -= 1
    P[p] += 1
    ret += "{:0=6}".format(p + 1)
    ret += "{:0=6}".format(P[p])
    ans[i] = ret
print(*ans, sep="\n")

-N, M = list(map(int, input().split())) -PY = [[0, 0, 0] for i in range(M)] -for i in range(M): -    P, Y = list(map(int, input().split())) -    PY[i] = [P, Y, i] +N, M = map(int, input().split()) +PY = [tuple(list(map(int, input().split())) + [i]) for i in range(M)] -PY.sort(key=lambda x: x[0]) -prev = 0 -for i in range(M): -    if PY[i][0] != prev: -        count = 1 -    else: -        count += 1 -    prev = PY[i][0] -    ans = ["0" for i in range(6 - len(str(prev)))] -    temp = ["0" for i in range(6 - len(str(count)))] -    ans += list(str(prev)) + temp + list(str(count)) -    PY[i][0] = "".join(ans) -PY.sort(key=lambda x: x[2]) -for i in range(M): -    print((PY[i][0])) +ans = [""] * M +P = [0] * N +for p, y, i in PY: +    ret = "" +    p -= 1 +    P[p] += 1 +    ret += "{:0=6}".format(p + 1) +    ret += "{:0=6}".format(P[p]) +    ans[i] = ret +print(*ans, sep="\n")