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



shi_map = []



for i in range(M):

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

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



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



result = {}

shi_count = {}

for i, p, y in shi_map:



    if p in shi_count:

        c = shi_count[p]

        count = c + 1

        shi_count[p] = count

    else:

        shi_count[p] = 1

        count = 1

    result[i] = [p, count]

result = list(sorted(list(result.items()), key=lambda x: x[0]))



for i, p in result:



    p2 = str(p[0]).zfill(6)



    y = str(p[1]).zfill(6)

    r = p2+y

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

items = []

for i in range(M):

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

    items.append((p, y, i))



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



ans = {}



ken = -1

cnt = 1

for item in items:

    if item[0] != ken:

        cnt = 1

        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6)

        ken = item[0]

    else:

        cnt += 1

        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6)



for i in range(M):

    print((ans[i]))

N, M = list(map(int, input().split()))
shi_map = []
for i in range(M):
    p, y = list(map(int, input().split()))
    shi_map.append([i, p, y])
shi_map = sorted(shi_map, key=lambda x: (x[1], x[2]))
result = {}
shi_count = {}
for i, p, y in shi_map:
    if p in shi_count:
        c = shi_count[p]
        count = c + 1
        shi_count[p] = count
    else:
        shi_count[p] = 1
        count = 1
    result[i] = [p, count]
result = list(sorted(list(result.items()), key=lambda x: x[0]))
for i, p in result:
    p2 = str(p[0]).zfill(6)
    y = str(p[1]).zfill(6)
    r = p2 + y
    print(r)

N, M = list(map(int, input().split()))
items = []
for i in range(M):
    p, y = list(map(int, input().split()))
    items.append((p, y, i))
items = sorted(items, key=lambda x: (x[0], x[1]))
ans = {}
ken = -1
cnt = 1
for item in items:
    if item[0] != ken:
        cnt = 1
        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6)
        ken = item[0]
    else:
        cnt += 1
        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6)
for i in range(M):
    print((ans[i]))

-shi_map = [] +items = [] -    shi_map.append([i, p, y]) -shi_map = sorted(shi_map, key=lambda x: (x[1], x[2])) -result = {} -shi_count = {} -for i, p, y in shi_map: -    if p in shi_count: -        c = shi_count[p] -        count = c + 1 -        shi_count[p] = count +    items.append((p, y, i)) +items = sorted(items, key=lambda x: (x[0], x[1])) +ans = {} +ken = -1 +cnt = 1 +for item in items: +    if item[0] != ken: +        cnt = 1 +        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6) +        ken = item[0] -        shi_count[p] = 1 -        count = 1 -    result[i] = [p, count] -result = list(sorted(list(result.items()), key=lambda x: x[0])) -for i, p in result: -    p2 = str(p[0]).zfill(6) -    y = str(p[1]).zfill(6) -    r = p2 + y -    print(r) +        cnt += 1 +        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6) +for i in range(M): +    print((ans[i]))