# ABC113C - ID

import sys

input = sys.stdin.readline



def main():

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

    P = [[] for _ in range(N + 1)]  # prefectures

    for num in range(M):

        pref, year = tuple(map(int, input().split()))

        P[pref] += [(year, num)]

    ans = []

    P = [sorted(p) for p in P]

    for pref_idx, pref in enumerate(P[1:], 1):

        if pref:

            for city_idx, (_, num) in enumerate(pref, 1):

                x = "{:06}{:06}".format(pref_idx, city_idx)

                ans += [(num, x)]

    print(*[i[1] for i in sorted(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)

    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 = tuple(map(int, input().split()))
    P = [[] for _ in range(N + 1)]  # prefectures
    for num in range(M):
        pref, year = tuple(map(int, input().split()))
        P[pref] += [(year, num)]
    ans = []
    P = [sorted(p) for p in P]
    for pref_idx, pref in enumerate(P[1:], 1):
        if pref:
            for city_idx, (_, num) in enumerate(pref, 1):
                x = "{:06}{:06}".format(pref_idx, city_idx)
                ans += [(num, x)]
    print(*[i[1] for i in sorted(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)
    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()

-    N, M = tuple(map(int, input().split())) -    P = [[] for _ in range(N + 1)]  # prefectures -    for num in range(M): -        pref, year = tuple(map(int, input().split())) -        P[pref] += [(year, num)] -    ans = [] -    P = [sorted(p) for p in P] -    for pref_idx, pref in enumerate(P[1:], 1): -        if pref: -            for city_idx, (_, num) in enumerate(pref, 1): -                x = "{:06}{:06}".format(pref_idx, city_idx) -                ans += [(num, x)] -    print(*[i[1] for i in sorted(ans)], sep="\n") +    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) +    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")