from collections import defaultdict

dic = defaultdict(int)

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

A = []

for i in range(M):

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

  A.append((a,b,i))

A.sort()

#print(A)

ans = [-1 for _ in range(M)]

for i in range(M):

  dic[A[i][0]] += 1

  #print(dic[A[i][0]])

  temp = "0"*(6-len(str(A[i][0])))+str(A[i][0])+"0"*(6-len(str(dic[A[i][0]])))+str(dic[A[i][0]])

  ans[A[i][2]] = temp

  #print(i,temp)

for t in ans:

  print(t)

  
import bisect

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

A = [[] for _ in range(N)] #重複がある場合にはsetにする？

original = []

for i in range(M):

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

  a-=1 #県を0indexに直す

  A[a].append(b)

  original.append((a,b))

for X in A:

  X.sort()

#print(A)

for i in range(M):

  ken,now = original[i]

  ID = bisect.bisect_left(A[ken],now)

  ken += 1; ID+=1

  ans = "0"*(6-len(str(ken)))+str(ken)+"0"*(6-len(str(ID)))+str(ID)

  print(ans)

from collections import defaultdict

dic = defaultdict(int)
N, M = list(map(int, input().split()))
A = []
for i in range(M):
    a, b = list(map(int, input().split()))
    A.append((a, b, i))
A.sort()
# print(A)
ans = [-1 for _ in range(M)]
for i in range(M):
    dic[A[i][0]] += 1
    # print(dic[A[i][0]])
    temp = (
        "0" * (6 - len(str(A[i][0])))
        + str(A[i][0])
        + "0" * (6 - len(str(dic[A[i][0]])))
        + str(dic[A[i][0]])
    )
    ans[A[i][2]] = temp
    # print(i,temp)
for t in ans:
    print(t)

import bisect

N, M = list(map(int, input().split()))
A = [[] for _ in range(N)]  # 重複がある場合にはsetにする？
original = []
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1  # 県を0indexに直す
    A[a].append(b)
    original.append((a, b))
for X in A:
    X.sort()
# print(A)
for i in range(M):
    ken, now = original[i]
    ID = bisect.bisect_left(A[ken], now)
    ken += 1
    ID += 1
    ans = "0" * (6 - len(str(ken))) + str(ken) + "0" * (6 - len(str(ID))) + str(ID)
    print(ans)

-from collections import defaultdict +import bisect -dic = defaultdict(int) -A = [] +A = [[] for _ in range(N)]  # 重複がある場合にはsetにする？ +original = [] -    A.append((a, b, i)) -A.sort() +    a -= 1  # 県を0indexに直す +    A[a].append(b) +    original.append((a, b)) +for X in A: +    X.sort() -ans = [-1 for _ in range(M)] -    dic[A[i][0]] += 1 -    # print(dic[A[i][0]]) -    temp = ( -        "0" * (6 - len(str(A[i][0]))) -        + str(A[i][0]) -        + "0" * (6 - len(str(dic[A[i][0]]))) -        + str(dic[A[i][0]]) -    ) -    ans[A[i][2]] = temp -    # print(i,temp) -for t in ans: -    print(t) +    ken, now = original[i] +    ID = bisect.bisect_left(A[ken], now) +    ken += 1 +    ID += 1 +    ans = "0" * (6 - len(str(ken))) + str(ken) + "0" * (6 - len(str(ID))) + str(ID) +    print(ans)