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()

def slove():

    import sys

    input = sys.stdin.readline

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

    py = []

    pyn = [1] * n

    for i in range(m):

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

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

    py.sort()

    for i in range(len(py)):

        py[i][1] = pyn[py[i][0]-1]

        pyn[py[i][0] - 1] += 1

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

    for p, y, i in py:

        l = ["0"] * (6 - len(str(p)))

        l.append(str(p))

        l.append("0" * (6 - len(str(y))))

        l.append(str(y))

        print(("".join(l)))







if __name__ == '__main__':

    slove()

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()

def slove():
    import sys

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


if __name__ == "__main__":
    slove()

-    ls = [1] * (n + 1) +    pyn = [1] * n -        py.append([p, y, 0, i]) +        py.append([p, y, i]) -    for i in range(m): -        py[i][2] = ls[py[i][0]] -        ls[py[i][0]] += 1 -    py.sort(key=lambda x: x[3]) -        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))) +        py[i][1] = pyn[py[i][0] - 1] +        pyn[py[i][0] - 1] += 1 +    py.sort(key=lambda x: x[2]) +    for p, y, i in py: +        l = ["0"] * (6 - len(str(p))) +        l.append(str(p)) +        l.append("0" * (6 - len(str(y)))) +        l.append(str(y)) +        print(("".join(l)))