# ABC113C - ID

import sys

input = sys.stdin.readline



def main():

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

    P = tuple(map(int, input().split()) for _ in range(M))

    A = sorted((p, y, i) for i, (p, y) in enumerate(P))

    ans, cnt = [""] * M, 1

    ans[A[0][2]] = "{:06}{:06}".format(A[0][0], cnt)

    for i in range(1, M):

        if A[i - 1][0] == A[i][0]:

            cnt += 1

        else:

            cnt = 1

        ans[A[i][2]] = "{:06}{:06}".format(A[i][0], cnt)

    print(*ans, sep="\n")





if __name__ == "__main__":

    main()

# ABC113C - ID

import sys

input = sys.stdin.readline



def main():

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

    ans, A, cnt = [""] * M, [], 1

    for i in range(M):

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

        A += [(p, y, i)]

    A.sort()

    ans[A[0][2]] = "{:06}{:06}".format(A[0][0], cnt)

    prev = A[0][0]

    for p, _, i in A[1:]:

        if prev == p:

            cnt += 1

        else:

            cnt = 1

        ans[i] = "{:06}{:06}".format(p, cnt)

        prev = p

    print(*ans, sep="\n")





if __name__ == "__main__":

    main()

# ABC113C - ID
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    P = tuple(map(int, input().split()) for _ in range(M))
    A = sorted((p, y, i) for i, (p, y) in enumerate(P))
    ans, cnt = [""] * M, 1
    ans[A[0][2]] = "{:06}{:06}".format(A[0][0], cnt)
    for i in range(1, M):
        if A[i - 1][0] == A[i][0]:
            cnt += 1
        else:
            cnt = 1
        ans[A[i][2]] = "{:06}{:06}".format(A[i][0], cnt)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

# ABC113C - ID
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    ans, A, cnt = [""] * M, [], 1
    for i in range(M):
        p, y = map(int, input().split())
        A += [(p, y, i)]
    A.sort()
    ans[A[0][2]] = "{:06}{:06}".format(A[0][0], cnt)
    prev = A[0][0]
    for p, _, i in A[1:]:
        if prev == p:
            cnt += 1
        else:
            cnt = 1
        ans[i] = "{:06}{:06}".format(p, cnt)
        prev = p
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

-    P = tuple(map(int, input().split()) for _ in range(M)) -    A = sorted((p, y, i) for i, (p, y) in enumerate(P)) -    ans, cnt = [""] * M, 1 +    ans, A, cnt = [""] * M, [], 1 +    for i in range(M): +        p, y = map(int, input().split()) +        A += [(p, y, i)] +    A.sort() -    for i in range(1, M): -        if A[i - 1][0] == A[i][0]: +    prev = A[0][0] +    for p, _, i in A[1:]: +        if prev == p: -        ans[A[i][2]] = "{:06}{:06}".format(A[i][0], cnt) +        ans[i] = "{:06}{:06}".format(p, cnt) +        prev = p