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

py = [list(map(int, (eval(input()) + " 0 " + str(i)).split())) for i in range(m)]

py = sorted(py, key=lambda x: (x[0], x[1]))

d = {}

for i, v in enumerate(py):

    if v[0] not in d:

        d[v[0]] = 1

    else:

        d[v[0]] += 1

    v[2] = d[v[0]]

py = sorted(py, key=lambda x: x[3])

for i in py:

    print((("000000" + str(i[0]))[-6:] + ("000000" + str(i[2]))[-6:]))

def slove():

    import sys

    input = sys.stdin.readline

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

    py = []

    ls = [1] * (n + 1)

    for i in range(m):

        p, y = list(map(int, input().rstrip('\n').split()))

        py.append([p, y, 0, i])

    py.sort()

    for i in range(m):

        py[i][2] = ls[py[i][0]]

        ls[py[i][0]] += 1

    py.sort(key=lambda x: x[3])

    for i in range(len(py)):

        a = ["0"] * 6

        a = a + list(str(py[i][0]))

        a = a[-6:]

        b = ["0"] * 6

        b = b + list(str(py[i][2]))

        b = b[-6:]

        print(("".join(a + b)))





if __name__ == '__main__':

    slove()

n, m = list(map(int, input().split()))
py = [list(map(int, (eval(input()) + " 0 " + str(i)).split())) for i in range(m)]
py = sorted(py, key=lambda x: (x[0], x[1]))
d = {}
for i, v in enumerate(py):
    if v[0] not in d:
        d[v[0]] = 1
    else:
        d[v[0]] += 1
    v[2] = d[v[0]]
py = sorted(py, key=lambda x: x[3])
for i in py:
    print((("000000" + str(i[0]))[-6:] + ("000000" + str(i[2]))[-6:]))

def slove():
    import sys

    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip("\n").split()))
    py = []
    ls = [1] * (n + 1)
    for i in range(m):
        p, y = list(map(int, input().rstrip("\n").split()))
        py.append([p, y, 0, i])
    py.sort()
    for i in range(m):
        py[i][2] = ls[py[i][0]]
        ls[py[i][0]] += 1
    py.sort(key=lambda x: x[3])
    for i in range(len(py)):
        a = ["0"] * 6
        a = a + list(str(py[i][0]))
        a = a[-6:]
        b = ["0"] * 6
        b = b + list(str(py[i][2]))
        b = b[-6:]
        print(("".join(a + b)))


if __name__ == "__main__":
    slove()

-n, m = list(map(int, input().split())) -py = [list(map(int, (eval(input()) + " 0 " + str(i)).split())) for i in range(m)] -py = sorted(py, key=lambda x: (x[0], x[1])) -d = {} -for i, v in enumerate(py): -    if v[0] not in d: -        d[v[0]] = 1 -    else: -        d[v[0]] += 1 -    v[2] = d[v[0]] -py = sorted(py, key=lambda x: x[3]) -for i in py: -    print((("000000" + str(i[0]))[-6:] + ("000000" + str(i[2]))[-6:])) +def slove(): +    import sys + +    input = sys.stdin.readline +    n, m = list(map(int, input().rstrip("\n").split())) +    py = [] +    ls = [1] * (n + 1) +    for i in range(m): +        p, y = list(map(int, input().rstrip("\n").split())) +        py.append([p, y, 0, i]) +    py.sort() +    for i in range(m): +        py[i][2] = ls[py[i][0]] +        ls[py[i][0]] += 1 +    py.sort(key=lambda x: x[3]) +    for i in range(len(py)): +        a = ["0"] * 6 +        a = a + list(str(py[i][0])) +        a = a[-6:] +        b = ["0"] * 6 +        b = b + list(str(py[i][2])) +        b = b[-6:] +        print(("".join(a + b))) + + +if __name__ == "__main__": +    slove()