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

city_list = [[] for _ in range(n)]



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



for ppyy in py:

  city_list[ppyy[0]-1].append(ppyy[1])



dict = {}

for index, ppyy in enumerate(city_list):

  ppyy.sort()

  for index2, pppyyy in enumerate(ppyy):

    dict[pppyyy] = (str(index+1).zfill(6)+str(index2+1).zfill(6))



for ppyy in py:

  print((dict[ppyy[1]]))
#!/usr/bin/env python3

import sys





def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):

    hashTable = {}



    for i in range(M):

        if hashTable.get(P[i]) == None:

            hashTable[P[i]] = [Y[i]]

        else:

            hashTable[P[i]].append(Y[i])

    

    # Year: idnumber

    answerTable = {}



    for key,value in list(hashTable.items()):

        value.sort()

        

        for i,v in enumerate(value):

            answerTable[v] = str(key).zfill(6) + str(i+1).zfill(6)

    

    for i in range(M):

        print((answerTable[Y[i]]))



    return





def main():

    def iterate_tokens():

        for line in sys.stdin:

            for word in line.split():

                yield word

    tokens = iterate_tokens()

    N = int(next(tokens))  # type: int

    M = int(next(tokens))  # type: int

    P = [int()] * (M)  # type: "List[int]"

    Y = [int()] * (M)  # type: "List[int]"

    for i in range(M):

        P[i] = int(next(tokens))

        Y[i] = int(next(tokens))

    solve(N, M, P, Y)



if __name__ == '__main__':

    main()

n, m = list(map(int, input().split()))
city_list = [[] for _ in range(n)]
py = [list(map(int, input().split())) for _ in range(m)]
for ppyy in py:
    city_list[ppyy[0] - 1].append(ppyy[1])
dict = {}
for index, ppyy in enumerate(city_list):
    ppyy.sort()
    for index2, pppyyy in enumerate(ppyy):
        dict[pppyyy] = str(index + 1).zfill(6) + str(index2 + 1).zfill(6)
for ppyy in py:
    print((dict[ppyy[1]]))

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    hashTable = {}
    for i in range(M):
        if hashTable.get(P[i]) == None:
            hashTable[P[i]] = [Y[i]]
        else:
            hashTable[P[i]].append(Y[i])
    # Year: idnumber
    answerTable = {}
    for key, value in list(hashTable.items()):
        value.sort()
        for i, v in enumerate(value):
            answerTable[v] = str(key).zfill(6) + str(i + 1).zfill(6)
    for i in range(M):
        print((answerTable[Y[i]]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, M, P, Y)


if __name__ == "__main__":
    main()

-n, m = list(map(int, input().split())) -city_list = [[] for _ in range(n)] -py = [list(map(int, input().split())) for _ in range(m)] -for ppyy in py: -    city_list[ppyy[0] - 1].append(ppyy[1]) -dict = {} -for index, ppyy in enumerate(city_list): -    ppyy.sort() -    for index2, pppyyy in enumerate(ppyy): -        dict[pppyyy] = str(index + 1).zfill(6) + str(index2 + 1).zfill(6) -for ppyy in py: -    print((dict[ppyy[1]])) +#!/usr/bin/env python3 +import sys + + +def solve(N: int, M: int, P: "List[int]", Y: "List[int]"): +    hashTable = {} +    for i in range(M): +        if hashTable.get(P[i]) == None: +            hashTable[P[i]] = [Y[i]] +        else: +            hashTable[P[i]].append(Y[i]) +    # Year: idnumber +    answerTable = {} +    for key, value in list(hashTable.items()): +        value.sort() +        for i, v in enumerate(value): +            answerTable[v] = str(key).zfill(6) + str(i + 1).zfill(6) +    for i in range(M): +        print((answerTable[Y[i]])) +    return + + +def main(): +    def iterate_tokens(): +        for line in sys.stdin: +            for word in line.split(): +                yield word + +    tokens = iterate_tokens() +    N = int(next(tokens))  # type: int +    M = int(next(tokens))  # type: int +    P = [int()] * (M)  # type: "List[int]" +    Y = [int()] * (M)  # type: "List[int]" +    for i in range(M): +        P[i] = int(next(tokens)) +        Y[i] = int(next(tokens)) +    solve(N, M, P, Y) + + +if __name__ == "__main__": +    main()