# ABC113C - ID

import sys

input = sys.stdin.readline



def main():

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

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

    for num in range(M):

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

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

    ans = []

    P = [sorted(p) for p in P]  # sort by year

    for pref_idx, pref in enumerate(P):

        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")  # sort by input order



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):  # classify cities by prefectures

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

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

    ans = [""] * M

    P = [sorted(p) for p in P]  # sort by year

    for pref_idx, pref in enumerate(P):

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

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

            ans[num] = x

    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 = [[] for _ in range(N + 1)]  # prefectures
    for num in range(M):
        pref, year = map(int, input().split())
        P[pref] += [(year, num)]
    ans = []
    P = [sorted(p) for p in P]  # sort by year
    for pref_idx, pref in enumerate(P):
        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")  # sort by input order


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


if __name__ == "__main__":
    main()

-    N, M = map(int, input().split()) +    N, M = tuple(map(int, input().split())) -    for num in range(M): -        pref, year = map(int, input().split()) +    for num in range(M):  # classify cities by prefectures +        pref, year = tuple(map(int, input().split())) -    ans = [] +    ans = [""] * M -            ans += [(num, x)] -    print(*[i[1] for i in sorted(ans)], sep="\n")  # sort by input order +            ans[num] = x +    print(*ans, sep="\n")