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

L = []

for i in range(M):

  L.append(list(map(int,input().split())))

for j in range(M):

  L[j].append(j)

L.sort()

l = L[0][0]

cnt = 0

for k in range(M):

  if l == L[k][0]:

    cnt += 1

    L[k].append(cnt)

  else:

    l = L[k][0]

    cnt = 1

    L[k].append(cnt)

L = sorted(L, key = lambda x:x[2])

for i in range(M):

  print(('0'*(6-len(str(L[i][0])))+str(L[i][0])+'0'*(6-len(str(L[i][3])))+str(L[i][3])))

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

L = []

for i in range(M):

  L.append(list(map(int,input().split())))

for i in range(M):

  L[i].append(i)

cnt = [0]*N

L = sorted(L, key = lambda x:x[1])

for i in range(M):

  L[i].append(cnt[L[i][0]-1])

  cnt[L[i][0]-1] += 1

L = sorted(L, key = lambda x:x[2])

for i in range(M):

  ID = str(L[i][0]).zfill(6)+str(L[i][3]+1).zfill(6)

  print(ID)
N, M = list(map(int, input().split()))
L = []
for i in range(M):
    L.append(list(map(int, input().split())))
for j in range(M):
    L[j].append(j)
L.sort()
l = L[0][0]
cnt = 0
for k in range(M):
    if l == L[k][0]:
        cnt += 1
        L[k].append(cnt)
    else:
        l = L[k][0]
        cnt = 1
        L[k].append(cnt)
L = sorted(L, key=lambda x: x[2])
for i in range(M):
    print(
        (
            "0" * (6 - len(str(L[i][0])))
            + str(L[i][0])
            + "0" * (6 - len(str(L[i][3])))
            + str(L[i][3])
        )
    )

N, M = list(map(int, input().split()))
L = []
for i in range(M):
    L.append(list(map(int, input().split())))
for i in range(M):
    L[i].append(i)
cnt = [0] * N
L = sorted(L, key=lambda x: x[1])
for i in range(M):
    L[i].append(cnt[L[i][0] - 1])
    cnt[L[i][0] - 1] += 1
L = sorted(L, key=lambda x: x[2])
for i in range(M):
    ID = str(L[i][0]).zfill(6) + str(L[i][3] + 1).zfill(6)
    print(ID)

-for j in range(M): -    L[j].append(j) -L.sort() -l = L[0][0] -cnt = 0 -for k in range(M): -    if l == L[k][0]: -        cnt += 1 -        L[k].append(cnt) -    else: -        l = L[k][0] -        cnt = 1 -        L[k].append(cnt) +for i in range(M): +    L[i].append(i) +cnt = [0] * N +L = sorted(L, key=lambda x: x[1]) +for i in range(M): +    L[i].append(cnt[L[i][0] - 1]) +    cnt[L[i][0] - 1] += 1 -    print( -        ( -            "0" * (6 - len(str(L[i][0]))) -            + str(L[i][0]) -            + "0" * (6 - len(str(L[i][3]))) -            + str(L[i][3]) -        ) -    ) +    ID = str(L[i][0]).zfill(6) + str(L[i][3] + 1).zfill(6) +    print(ID)