import sys

input = sys.stdin.readline





def binary_search(list, item):

    low = 0

    high = len(list) - 1



    while low <= high:

        mid = (low + high) // 2

        guess = list[mid]

        if guess == item:

            return mid

        if guess > item:

            high = mid - 1

        else:

            low = mid + 1





n, m = list(map(int, input().split()))

py = [list(map(int, input().split())) for i in range(m)]

check = sorted(py)

memo = py[0][0]

cnt = [0] * m

cnt_memo = 0



for i in range(m):

    if memo != check[i][0]:

        memo = check[i][0]

        cnt_memo = 0

    cnt_memo += 1

    cnt[i] = cnt_memo



for i in range(m):

    number = str(cnt[binary_search(check, py[i])])

    p = str(py[i][0])

    print(((6 - len(p)) * '0' + p + (6 - len(number)) * '0' + number))

import sys

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines

sys.setrecursionlimit(10 ** 7)



from bisect import bisect_left



n, m = list(map(int, readline().split()))

py = [list(map(int, readline().split())) for _ in range(m)]

check = sorted(py)

idx = [0] * (n + 1)

memo = 0

for i, (p, _) in enumerate(check):

    if memo != p:

        idx[p] = i

        memo = p

for p, y in py:

    yy = str(bisect_left(check, [p, y]) - idx[p] + 1)

    p = str(p)

    print(('0' * (6 - len(p)) + p + '0' * (6 - len(yy)) + yy))

import sys

input = sys.stdin.readline


def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1


n, m = list(map(int, input().split()))
py = [list(map(int, input().split())) for i in range(m)]
check = sorted(py)
memo = py[0][0]
cnt = [0] * m
cnt_memo = 0
for i in range(m):
    if memo != check[i][0]:
        memo = check[i][0]
        cnt_memo = 0
    cnt_memo += 1
    cnt[i] = cnt_memo
for i in range(m):
    number = str(cnt[binary_search(check, py[i])])
    p = str(py[i][0])
    print(((6 - len(p)) * "0" + p + (6 - len(number)) * "0" + number))

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**7)
from bisect import bisect_left

n, m = list(map(int, readline().split()))
py = [list(map(int, readline().split())) for _ in range(m)]
check = sorted(py)
idx = [0] * (n + 1)
memo = 0
for i, (p, _) in enumerate(check):
    if memo != p:
        idx[p] = i
        memo = p
for p, y in py:
    yy = str(bisect_left(check, [p, y]) - idx[p] + 1)
    p = str(p)
    print(("0" * (6 - len(p)) + p + "0" * (6 - len(yy)) + yy))

-input = sys.stdin.readline +read = sys.stdin.buffer.read +readline = sys.stdin.buffer.readline +readlines = sys.stdin.buffer.readlines +sys.setrecursionlimit(10**7) +from bisect import bisect_left - -def binary_search(list, item): -    low = 0 -    high = len(list) - 1 -    while low <= high: -        mid = (low + high) // 2 -        guess = list[mid] -        if guess == item: -            return mid -        if guess > item: -            high = mid - 1 -        else: -            low = mid + 1 - - -n, m = list(map(int, input().split())) -py = [list(map(int, input().split())) for i in range(m)] +n, m = list(map(int, readline().split())) +py = [list(map(int, readline().split())) for _ in range(m)] -memo = py[0][0] -cnt = [0] * m -cnt_memo = 0 -for i in range(m): -    if memo != check[i][0]: -        memo = check[i][0] -        cnt_memo = 0 -    cnt_memo += 1 -    cnt[i] = cnt_memo -for i in range(m): -    number = str(cnt[binary_search(check, py[i])]) -    p = str(py[i][0]) -    print(((6 - len(p)) * "0" + p + (6 - len(number)) * "0" + number)) +idx = [0] * (n + 1) +memo = 0 +for i, (p, _) in enumerate(check): +    if memo != p: +        idx[p] = i +        memo = p +for p, y in py: +    yy = str(bisect_left(check, [p, y]) - idx[p] + 1) +    p = str(p) +    print(("0" * (6 - len(p)) + p + "0" * (6 - len(yy)) + yy))