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



city = [[] for i in range(M)]

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

count = [0] * N



for i in range(M):

    city[i] = list(map(int, input().split())) + [i]



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



for i in range(M):

     ken, year, num = city[i]

     count[ken-1] += 1

     city_id[num] = "{:0=6}{:0=6}".format(ken, count[ken-1])



for i in range(M):

    print((city_id[i]))

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

py = sorted([list(map(int, input().split()))+[i] for i in range(M)], key=lambda x:x[1])

count = [1] * N

ans = [None] * M



for i in range(M):

  p, y, num = py[i]

  ans[num] = "{:0>6}{:0>6}".format(p, count[p-1])

  count[p-1] += 1



for i in range(M):

  print((ans[i]))
N, M = list(map(int, input().split()))
city = [[] for i in range(M)]
city_id = ["" for i in range(M)]
count = [0] * N
for i in range(M):
    city[i] = list(map(int, input().split())) + [i]
city = sorted(city, key=lambda x: (x[0], x[1]))
for i in range(M):
    ken, year, num = city[i]
    count[ken - 1] += 1
    city_id[num] = "{:0=6}{:0=6}".format(ken, count[ken - 1])
for i in range(M):
    print((city_id[i]))

N, M = list(map(int, input().split()))
py = sorted(
    [list(map(int, input().split())) + [i] for i in range(M)], key=lambda x: x[1]
)
count = [1] * N
ans = [None] * M
for i in range(M):
    p, y, num = py[i]
    ans[num] = "{:0>6}{:0>6}".format(p, count[p - 1])
    count[p - 1] += 1
for i in range(M):
    print((ans[i]))

-city = [[] for i in range(M)] -city_id = ["" for i in range(M)] -count = [0] * N +py = sorted( +    [list(map(int, input().split())) + [i] for i in range(M)], key=lambda x: x[1] +) +count = [1] * N +ans = [None] * M -    city[i] = list(map(int, input().split())) + [i] -city = sorted(city, key=lambda x: (x[0], x[1])) +    p, y, num = py[i] +    ans[num] = "{:0>6}{:0>6}".format(p, count[p - 1]) +    count[p - 1] += 1 -    ken, year, num = city[i] -    count[ken - 1] += 1 -    city_id[num] = "{:0=6}{:0=6}".format(ken, count[ken - 1]) -for i in range(M): -    print((city_id[i])) +    print((ans[i]))