def main():

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

    X = [list(map(int,input().split())) for _ in range(M)]

    for i in range(M):

        X[i].append(i)



    X.sort(key=lambda X:(X[0],X[1]))

    anslist = [[0,0] for _ in range(M)]

    tmp = 0

    count = 1

    for i in range(M):

        if tmp != X[i][0]:

            tmp = X[i][0]

            count = 1

            anslist[i][0] = "0"*(6-len(str(X[i][0])))+str(X[i][0])+"0"*(6-len(str(count)))+str(count)

            anslist[i][1] = X[i][2]

        else:

            count += 1

            anslist[i][0] = "0"*(6-len(str(X[i][0])))+str(X[i][0])+"0"*(6-len(str(count)))+str(count)

            anslist[i][1] = X[i][2]

            

    anslist.sort(key=lambda X:X[1])

    for i in range(M):

        print((anslist[i][0]))



if __name__ == "__main__":

    main()
from operator import itemgetter

import sys

input = sys.stdin.readline



def main():

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

    f = []

    for i in range(M):

        P,Y = list(map(int,input().split()))

        f.append([P,Y,i])

        

    f.sort(key = itemgetter(0,1))

    s = 1

    count = 0

    for i in range(M):

        if s != f[i][0]:

            s = f[i][0]

            count = 1

            f[i][1] = count

        else:

            count += 1

            f[i][1] = count

            

    ans = []

    for i in range(M):

        p,y,num = f[i]

        lp,ly = len(str(p)),len(str(y))

        ad = "0"*(6-lp) + str(p) + "0"*(6-ly) + str(y)

        ans.append((num,ad))

        

    ans.sort(key = itemgetter(0))

    for i in range(M):print((ans[i][1]))

    

if __name__ == "__main__":

    main()

def main():
    N, M = list(map(int, input().split()))
    X = [list(map(int, input().split())) for _ in range(M)]
    for i in range(M):
        X[i].append(i)
    X.sort(key=lambda X: (X[0], X[1]))
    anslist = [[0, 0] for _ in range(M)]
    tmp = 0
    count = 1
    for i in range(M):
        if tmp != X[i][0]:
            tmp = X[i][0]
            count = 1
            anslist[i][0] = (
                "0" * (6 - len(str(X[i][0])))
                + str(X[i][0])
                + "0" * (6 - len(str(count)))
                + str(count)
            )
            anslist[i][1] = X[i][2]
        else:
            count += 1
            anslist[i][0] = (
                "0" * (6 - len(str(X[i][0])))
                + str(X[i][0])
                + "0" * (6 - len(str(count)))
                + str(count)
            )
            anslist[i][1] = X[i][2]
    anslist.sort(key=lambda X: X[1])
    for i in range(M):
        print((anslist[i][0]))


if __name__ == "__main__":
    main()

from operator import itemgetter
import sys

input = sys.stdin.readline


def main():
    N, M = list(map(int, input().split()))
    f = []
    for i in range(M):
        P, Y = list(map(int, input().split()))
        f.append([P, Y, i])
    f.sort(key=itemgetter(0, 1))
    s = 1
    count = 0
    for i in range(M):
        if s != f[i][0]:
            s = f[i][0]
            count = 1
            f[i][1] = count
        else:
            count += 1
            f[i][1] = count
    ans = []
    for i in range(M):
        p, y, num = f[i]
        lp, ly = len(str(p)), len(str(y))
        ad = "0" * (6 - lp) + str(p) + "0" * (6 - ly) + str(y)
        ans.append((num, ad))
    ans.sort(key=itemgetter(0))
    for i in range(M):
        print((ans[i][1]))


if __name__ == "__main__":
    main()

+from operator import itemgetter +import sys + +input = sys.stdin.readline + + -    X = [list(map(int, input().split())) for _ in range(M)] +    f = [] -        X[i].append(i) -    X.sort(key=lambda X: (X[0], X[1])) -    anslist = [[0, 0] for _ in range(M)] -    tmp = 0 -    count = 1 +        P, Y = list(map(int, input().split())) +        f.append([P, Y, i]) +    f.sort(key=itemgetter(0, 1)) +    s = 1 +    count = 0 -        if tmp != X[i][0]: -            tmp = X[i][0] +        if s != f[i][0]: +            s = f[i][0] -            anslist[i][0] = ( -                "0" * (6 - len(str(X[i][0]))) -                + str(X[i][0]) -                + "0" * (6 - len(str(count))) -                + str(count) -            ) -            anslist[i][1] = X[i][2] +            f[i][1] = count -            anslist[i][0] = ( -                "0" * (6 - len(str(X[i][0]))) -                + str(X[i][0]) -                + "0" * (6 - len(str(count))) -                + str(count) -            ) -            anslist[i][1] = X[i][2] -    anslist.sort(key=lambda X: X[1]) +            f[i][1] = count +    ans = [] -        print((anslist[i][0])) +        p, y, num = f[i] +        lp, ly = len(str(p)), len(str(y)) +        ad = "0" * (6 - lp) + str(p) + "0" * (6 - ly) + str(y) +        ans.append((num, ad)) +    ans.sort(key=itemgetter(0)) +    for i in range(M): +        print((ans[i][1]))