import sys

import math  # noqa

import bisect  # noqa

import queue  # noqa





def input():

    return sys.stdin.readline().rstrip()





if __name__ == '__main__':

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

    PY = []

    for i in range(M):

        P, Y = list(map(int, input().split()))

        PY.append([Y, P, i + 1])

    PY.sort()



    # cnt: key=県, value=すでに幾つの市がその県に属しているか

    # res: [市の番号, 県の番号, 順番]

    cnt = {}

    res = []

    for y, p, i in PY:

        if p not in cnt:

            cnt[p] = 1

        else:

            cnt[p] += 1

        res.append([i, p, cnt[p]])



    res.sort()

    for i, p, x in res:

        print(('{:06}{:06}'.format(p, x)))

import sys

import math  # noqa

import bisect  # noqa

import queue  # noqa





if __name__ == '__main__':

    N, M = list(map(int, sys.stdin.readline().rstrip().split()))

    PY = []

    for i in range(M):

        P, Y = list(map(int, sys.stdin.readline().rstrip().split()))

        PY.append([Y, P, i + 1])

    PY.sort()



    # cnt: key=県, value=すでに幾つの市がその県に属しているか

    # res: [市の番号, 県の番号, 順番]

    cnt = {}

    res = []

    for y, p, i in PY:

        if p not in cnt:

            cnt[p] = 1

        else:

            cnt[p] += 1

        res.append([i, p, cnt[p]])



    res.sort()

    for i, p, x in res:

        print(('{:06}{:06}'.format(p, x)))

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    PY = []
    for i in range(M):
        P, Y = list(map(int, input().split()))
        PY.append([Y, P, i + 1])
    PY.sort()
    # cnt: key=県, value=すでに幾つの市がその県に属しているか
    # res: [市の番号, 県の番号, 順番]
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])
    res.sort()
    for i, p, x in res:
        print(("{:06}{:06}".format(p, x)))

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa

if __name__ == "__main__":
    N, M = list(map(int, sys.stdin.readline().rstrip().split()))
    PY = []
    for i in range(M):
        P, Y = list(map(int, sys.stdin.readline().rstrip().split()))
        PY.append([Y, P, i + 1])
    PY.sort()
    # cnt: key=県, value=すでに幾つの市がその県に属しているか
    # res: [市の番号, 県の番号, 順番]
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])
    res.sort()
    for i, p, x in res:
        print(("{:06}{:06}".format(p, x)))

- -def input(): -    return sys.stdin.readline().rstrip() - - -    N, M = list(map(int, input().split())) +    N, M = list(map(int, sys.stdin.readline().rstrip().split())) -        P, Y = list(map(int, input().split())) +        P, Y = list(map(int, sys.stdin.readline().rstrip().split()))