import numpy as np





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

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

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

for _p, _y in py:

    p[_p - 1].append(_y)

for i in range(n):

    p[i] = np.argsort(np.argsort(p[i]))



counter = [0 for _ in range(n)]

for _p, _y in py:

    t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)

    print(t)

    counter[_p - 1] += 1

import numpy as np





def solve(string):



    n, m, *py = list(map(int, string.split()))

    py = [(_p, _y) for _p, _y in zip(py[0::2], py[1::2])]

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

    for _p, _y in py:

        p[_p - 1].append(_y)

    for i in range(n):

        p[i] = np.argsort(np.argsort(p[i]))



    counter = [0 for _ in range(n)]

    ans = []

    for _p, _y in py:

        ans.append("{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1))

        counter[_p - 1] += 1

    return "\n".join(ans)





if __name__ == '__main__':

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

    print((solve("{} {}\n".format(n, m) + "\n".join([eval(input()) for _ in range(m)]))))

import numpy as np

n, m = list(map(int, input().split()))
py = [list(map(int, input().split())) for _ in range(m)]
p = [[] for _ in range(n)]
for _p, _y in py:
    p[_p - 1].append(_y)
for i in range(n):
    p[i] = np.argsort(np.argsort(p[i]))
counter = [0 for _ in range(n)]
for _p, _y in py:
    t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)
    print(t)
    counter[_p - 1] += 1

import numpy as np


def solve(string):
    n, m, *py = list(map(int, string.split()))
    py = [(_p, _y) for _p, _y in zip(py[0::2], py[1::2])]
    p = [[] for _ in range(n)]
    for _p, _y in py:
        p[_p - 1].append(_y)
    for i in range(n):
        p[i] = np.argsort(np.argsort(p[i]))
    counter = [0 for _ in range(n)]
    ans = []
    for _p, _y in py:
        ans.append("{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1))
        counter[_p - 1] += 1
    return "\n".join(ans)


if __name__ == "__main__":
    n, m = list(map(int, input().split()))
    print(
        (solve("{} {}\n".format(n, m) + "\n".join([eval(input()) for _ in range(m)])))
    )

-n, m = list(map(int, input().split())) -py = [list(map(int, input().split())) for _ in range(m)] -p = [[] for _ in range(n)] -for _p, _y in py: -    p[_p - 1].append(_y) -for i in range(n): -    p[i] = np.argsort(np.argsort(p[i])) -counter = [0 for _ in range(n)] -for _p, _y in py: -    t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1) -    print(t) -    counter[_p - 1] += 1 + +def solve(string): +    n, m, *py = list(map(int, string.split())) +    py = [(_p, _y) for _p, _y in zip(py[0::2], py[1::2])] +    p = [[] for _ in range(n)] +    for _p, _y in py: +        p[_p - 1].append(_y) +    for i in range(n): +        p[i] = np.argsort(np.argsort(p[i])) +    counter = [0 for _ in range(n)] +    ans = [] +    for _p, _y in py: +        ans.append("{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)) +        counter[_p - 1] += 1 +    return "\n".join(ans) + + +if __name__ == "__main__": +    n, m = list(map(int, input().split())) +    print( +        (solve("{} {}\n".format(n, m) + "\n".join([eval(input()) for _ in range(m)]))) +    )