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

P = []

Y = []

arr = [[]for j in range(10**5+1)]

for i in range(M):

  listA = list(map(int,input().split()))

  P.append(listA[0])

  Y.append(listA[1])

  arr[listA[0]].append(listA[1])

for i in range(N+1):

  arr[i].sort()

for i in range(M):

  #二部探索

  left = 0

  right = len(arr[P[i]])-1

  while left <= right:

    mid = (left+right)//2

    if arr[P[i]][mid] == Y[i]:

      k = mid

      break

    elif arr[P[i]][mid] > Y[i]:

      right = mid-1

    else:

      left = mid+1

  print((str(P[i]).rjust(6,'0')+str(k+1).rjust(6,'0')))
N,M = list(map(int,input().split()))

A = []

for i in range(M):

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

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

A.sort(key=lambda x:(x[0],x[1]))

ans = ["" for i in range(M)]

p = -1

y = 1

for a in A:

    if p!=a[0]:

        y = 1

        p = a[0]

    b = "0"*(6-len(str(a[0])))+str(a[0])+"0"*(6-len(str(y)))+str(y)

    ans[a[2]] = b

    y+=1

for i in ans:

    print(i)
N, M = list(map(int, input().split()))
P = []
Y = []
arr = [[] for j in range(10**5 + 1)]
for i in range(M):
    listA = list(map(int, input().split()))
    P.append(listA[0])
    Y.append(listA[1])
    arr[listA[0]].append(listA[1])
for i in range(N + 1):
    arr[i].sort()
for i in range(M):
    # 二部探索
    left = 0
    right = len(arr[P[i]]) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[P[i]][mid] == Y[i]:
            k = mid
            break
        elif arr[P[i]][mid] > Y[i]:
            right = mid - 1
        else:
            left = mid + 1
    print((str(P[i]).rjust(6, "0") + str(k + 1).rjust(6, "0")))

N, M = list(map(int, input().split()))
A = []
for i in range(M):
    p, y = list(map(int, input().split()))
    A.append([p, y, i])
A.sort(key=lambda x: (x[0], x[1]))
ans = ["" for i in range(M)]
p = -1
y = 1
for a in A:
    if p != a[0]:
        y = 1
        p = a[0]
    b = "0" * (6 - len(str(a[0]))) + str(a[0]) + "0" * (6 - len(str(y))) + str(y)
    ans[a[2]] = b
    y += 1
for i in ans:
    print(i)

-P = [] -Y = [] -arr = [[] for j in range(10**5 + 1)] +A = [] -    listA = list(map(int, input().split())) -    P.append(listA[0]) -    Y.append(listA[1]) -    arr[listA[0]].append(listA[1]) -for i in range(N + 1): -    arr[i].sort() -for i in range(M): -    # 二部探索 -    left = 0 -    right = len(arr[P[i]]) - 1 -    while left <= right: -        mid = (left + right) // 2 -        if arr[P[i]][mid] == Y[i]: -            k = mid -            break -        elif arr[P[i]][mid] > Y[i]: -            right = mid - 1 -        else: -            left = mid + 1 -    print((str(P[i]).rjust(6, "0") + str(k + 1).rjust(6, "0"))) +    p, y = list(map(int, input().split())) +    A.append([p, y, i]) +A.sort(key=lambda x: (x[0], x[1])) +ans = ["" for i in range(M)] +p = -1 +y = 1 +for a in A: +    if p != a[0]: +        y = 1 +        p = a[0] +    b = "0" * (6 - len(str(a[0]))) + str(a[0]) + "0" * (6 - len(str(y))) + str(y) +    ans[a[2]] = b +    y += 1 +for i in ans: +    print(i)