import sys

import bisect

input = sys.stdin.readline



def main():

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

    PY_input = []

    PY_dict = {}

    for _ in range(M):

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

        PY_input.append((p, y))

        PY_dict.setdefault(p, []).append(y)



    for i in list(PY_dict.values()):

        i.sort()



    for p, y in PY_input:

        print(("{:06}{:06}".format(p, bisect.bisect_right(PY_dict[p], y))))





if __name__ == "__main__":

    main()

import sys

import bisect

read = sys.stdin.read

readline = sys.stdin.readline



def main2():

    N,M,*PY = list(map(int, read().split()))

    PY_input = []

    PY_dict = {}

    for p, y in zip(*[iter(PY)]*2):

        PY_input.append((p, y))

        PY_dict.setdefault(p, []).append(y)



    for i in list(PY_dict.values()):

        i.sort()



    for p, y in PY_input:

        print(("{:06}{:06}".format(p, bisect.bisect_right(PY_dict[p], y))))





if __name__ == "__main__":

    main2()
import sys
import bisect

input = sys.stdin.readline


def main():
    N, M = list(map(int, input().split()))
    PY_input = []
    PY_dict = {}
    for _ in range(M):
        p, y = list(map(int, input().split()))
        PY_input.append((p, y))
        PY_dict.setdefault(p, []).append(y)
    for i in list(PY_dict.values()):
        i.sort()
    for p, y in PY_input:
        print(("{:06}{:06}".format(p, bisect.bisect_right(PY_dict[p], y))))


if __name__ == "__main__":
    main()

import sys
import bisect

read = sys.stdin.read
readline = sys.stdin.readline


def main2():
    N, M, *PY = list(map(int, read().split()))
    PY_input = []
    PY_dict = {}
    for p, y in zip(*[iter(PY)] * 2):
        PY_input.append((p, y))
        PY_dict.setdefault(p, []).append(y)
    for i in list(PY_dict.values()):
        i.sort()
    for p, y in PY_input:
        print(("{:06}{:06}".format(p, bisect.bisect_right(PY_dict[p], y))))


if __name__ == "__main__":
    main2()

-input = sys.stdin.readline +read = sys.stdin.read +readline = sys.stdin.readline -def main(): -    N, M = list(map(int, input().split())) +def main2(): +    N, M, *PY = list(map(int, read().split())) -    for _ in range(M): -        p, y = list(map(int, input().split())) +    for p, y in zip(*[iter(PY)] * 2): -    main() +    main2()