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

for b in B:

    print(b)
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

    for b in B:

        print(b)





if __name__ == '__main__':

    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
for b in B:
    print(b)

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
    for b in B:
        print(b)


if __name__ == "__main__":
    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 -for b in B: -    print(b) +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 +    for b in B: +        print(b) + + +if __name__ == "__main__": +    main()