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

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



groups = [[] for _ in range(N + 1)]

for p, y in PY:

	groups[p] += [y]



for i, g in enumerate(groups):

	g.sort()

	cities = {}

	for j, t in enumerate(g):

		cities[t] = j + 1

	groups[i] = cities



for p, y in PY:

	print(("{:06d}{:06d}".format(p, groups[p][y])))

import sys

from math import factorial, ceil, floor

from bisect import bisect_right as bsr

from operator import itemgetter as ig

from collections import defaultdict as dd

from collections import deque



# お約束

args = None

INF = float("inf")

MOD = int(1e9 + 7)

def input(*ps):

    if len(ps) == 0:

        return next(args)

    elif type(ps[0]) is list:

        return [eval(input(*ps[0][0])) for _ in range(ps[0][1])]

    elif len(ps) == 1:

        return ps[0](next(args))

    else:

        return [p(next(args)) for p in ps]



# エントリーポイント

def main():

    N, M = eval(input(int, int))



    ps = dd(list)

    for i in range(M):

        p, y = eval(input(int, int))

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

    ans = [None] * M

    for k, v in list(ps.items()):

        v.sort()

        for i, c in enumerate(v, start=1):

            ans[c[1]] = (k, i)

    for v in ans:

        print(("{:06d}{:06d}".format(v[0], v[1])))



if __name__ == '__main__':

    args = iter(sys.stdin.read().split())

    main()

N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) for _ in range(M)]
groups = [[] for _ in range(N + 1)]
for p, y in PY:
    groups[p] += [y]
for i, g in enumerate(groups):
    g.sort()
    cities = {}
    for j, t in enumerate(g):
        cities[t] = j + 1
    groups[i] = cities
for p, y in PY:
    print(("{:06d}{:06d}".format(p, groups[p][y])))

import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if len(ps) == 0:
        return next(args)
    elif type(ps[0]) is list:
        return [eval(input(*ps[0][0])) for _ in range(ps[0][1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


# エントリーポイント
def main():
    N, M = eval(input(int, int))
    ps = dd(list)
    for i in range(M):
        p, y = eval(input(int, int))
        ps[p].append((y, i))
    ans = [None] * M
    for k, v in list(ps.items()):
        v.sort()
        for i, c in enumerate(v, start=1):
            ans[c[1]] = (k, i)
    for v in ans:
        print(("{:06d}{:06d}".format(v[0], v[1])))


if __name__ == "__main__":
    args = iter(sys.stdin.read().split())
    main()

-N, M = list(map(int, input().split())) -PY = [list(map(int, input().split())) for _ in range(M)] -groups = [[] for _ in range(N + 1)] -for p, y in PY: -    groups[p] += [y] -for i, g in enumerate(groups): -    g.sort() -    cities = {} -    for j, t in enumerate(g): -        cities[t] = j + 1 -    groups[i] = cities -for p, y in PY: -    print(("{:06d}{:06d}".format(p, groups[p][y]))) +import sys +from math import factorial, ceil, floor +from bisect import bisect_right as bsr +from operator import itemgetter as ig +from collections import defaultdict as dd +from collections import deque + +# お約束 +args = None +INF = float("inf") +MOD = int(1e9 + 7) + + +def input(*ps): +    if len(ps) == 0: +        return next(args) +    elif type(ps[0]) is list: +        return [eval(input(*ps[0][0])) for _ in range(ps[0][1])] +    elif len(ps) == 1: +        return ps[0](next(args)) +    else: +        return [p(next(args)) for p in ps] + + +# エントリーポイント +def main(): +    N, M = eval(input(int, int)) +    ps = dd(list) +    for i in range(M): +        p, y = eval(input(int, int)) +        ps[p].append((y, i)) +    ans = [None] * M +    for k, v in list(ps.items()): +        v.sort() +        for i, c in enumerate(v, start=1): +            ans[c[1]] = (k, i) +    for v in ans: +        print(("{:06d}{:06d}".format(v[0], v[1]))) + + +if __name__ == "__main__": +    args = iter(sys.stdin.read().split()) +    main()