import sys

input = sys.stdin.readline



def main():

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

    A = []

    B = [''] * m

    for i in range(m):

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

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

    A.sort()

    count = 0

    i, x = 1, 1

    for a in A:

        if a[0] == i:

            B[a[2]] = '{:06}{:06}'.format(a[0], x)

        else:

            i, x = a[0], 1

            B[a[2]] = '{:06}{:06}'.format(a[0], x)

        x += 1

    print(('\n'.join(B)))





if __name__ == '__main__':

    main()
import sys

input = sys.stdin.readline



def main():

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

    A = []

    B = [''] * m

    for i in range(m):

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

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

    A.sort()

    count = 0

    i, x = 1, 1

    for a in A:

        if a[0] == i:

            B[a[2]] = '{:06}{:06}'.format(a[0], x)

        else:

            i, x = a[0], 1

            B[a[2]] = '{:06}{:06}'.format(a[0], x)

        x += 1

    print(('\n'.join(B)))





if __name__ == '__main__':

    main()
import sys

input = sys.stdin.readline


def main():
    n, m = list(map(int, input().split()))
    A = []
    B = [""] * m
    for i in range(m):
        p, y = list(map(int, input().split()))
        A.append([p, y, i])
    A.sort()
    count = 0
    i, x = 1, 1
    for a in A:
        if a[0] == i:
            B[a[2]] = "{:06}{:06}".format(a[0], x)
        else:
            i, x = a[0], 1
            B[a[2]] = "{:06}{:06}".format(a[0], x)
        x += 1
    print(("\n".join(B)))


if __name__ == "__main__":
    main()

import sys

input = sys.stdin.readline


def main():
    n, m = list(map(int, input().split()))
    A = []
    B = [""] * m
    for i in range(m):
        p, y = list(map(int, input().split()))
        A += [(p, y, i)]
    A.sort()
    count = 0
    i, x = 1, 1
    for a in A:
        if a[0] == i:
            B[a[2]] = "{:06}{:06}".format(a[0], x)
        else:
            i, x = a[0], 1
            B[a[2]] = "{:06}{:06}".format(a[0], x)
        x += 1
    print(("\n".join(B)))


if __name__ == "__main__":
    main()

-        A.append([p, y, i]) +        A += [(p, y, i)]