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

pref = [1] * (N + 1)

iPY = []

for i in range(M):

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

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



iPY.sort(key=lambda x: x[2])

ans = []

for i, p, y in iPY:

    name = str(p).zfill(6) + str(pref[p]).zfill(6)

    ans.append((i, name))

    pref[p] += 1



ans.sort(key=lambda x: x[0])

for _, name in ans:

    print(name)

import bisect

import sys





sys.setrecursionlimit(10 ** 6)

INF = float("inf")

MOD = 10 ** 9 + 7





def input():

    return sys.stdin.readline().strip()





def main():

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

    d = [[] for _ in range(N + 1)]

    PY = []

    for _ in range(M):

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

        d[p].append(y)

        PY.append((p, y))



    for i in range(N + 1):

        if not d[i]:

            continue

        d[i] = sorted(set(d[i]))



    for p, y in PY:

        order = bisect.bisect_left(d[p], y)

        print((str(p).zfill(6) + str(order + 1).zfill(6)))





if __name__ == "__main__":

    main()

N, M = list(map(int, input().split()))
pref = [1] * (N + 1)
iPY = []
for i in range(M):
    p, y = list(map(int, input().split()))
    iPY.append([i, p, y])
iPY.sort(key=lambda x: x[2])
ans = []
for i, p, y in iPY:
    name = str(p).zfill(6) + str(pref[p]).zfill(6)
    ans.append((i, name))
    pref[p] += 1
ans.sort(key=lambda x: x[0])
for _, name in ans:
    print(name)

import bisect
import sys

sys.setrecursionlimit(10**6)
INF = float("inf")
MOD = 10**9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = list(map(int, input().split()))
    d = [[] for _ in range(N + 1)]
    PY = []
    for _ in range(M):
        p, y = list(map(int, input().split()))
        d[p].append(y)
        PY.append((p, y))
    for i in range(N + 1):
        if not d[i]:
            continue
        d[i] = sorted(set(d[i]))
    for p, y in PY:
        order = bisect.bisect_left(d[p], y)
        print((str(p).zfill(6) + str(order + 1).zfill(6)))


if __name__ == "__main__":
    main()

-N, M = list(map(int, input().split())) -pref = [1] * (N + 1) -iPY = [] -for i in range(M): -    p, y = list(map(int, input().split())) -    iPY.append([i, p, y]) -iPY.sort(key=lambda x: x[2]) -ans = [] -for i, p, y in iPY: -    name = str(p).zfill(6) + str(pref[p]).zfill(6) -    ans.append((i, name)) -    pref[p] += 1 -ans.sort(key=lambda x: x[0]) -for _, name in ans: -    print(name) +import bisect +import sys + +sys.setrecursionlimit(10**6) +INF = float("inf") +MOD = 10**9 + 7 + + +def input(): +    return sys.stdin.readline().strip() + + +def main(): +    N, M = list(map(int, input().split())) +    d = [[] for _ in range(N + 1)] +    PY = [] +    for _ in range(M): +        p, y = list(map(int, input().split())) +        d[p].append(y) +        PY.append((p, y)) +    for i in range(N + 1): +        if not d[i]: +            continue +        d[i] = sorted(set(d[i])) +    for p, y in PY: +        order = bisect.bisect_left(d[p], y) +        print((str(p).zfill(6) + str(order + 1).zfill(6))) + + +if __name__ == "__main__": +    main()