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

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



spy = sorted(py)



signate = {}

cnt = 0

last_p = 0

for p, y in spy:

    pref = "{:06}".format(p)

    if last_p == p:

        cnt += 1

    else:

        last_p = p

        cnt = 1

    year = "{:06}".format(cnt)

    signate["{}-{}".format(p, y)] = pref+year



for p, y in py:

    print((signate['{}-{}'.format(p, y)]))

import bisect

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

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

PY = []

for _ in range(m):

    p, y = list(map(int, input().split()))

    Ps[p-1].append(y)

    PY.append((p, y))



for ls in Ps:

    ls.sort()



for p, y in PY:

    pid = "{:06}".format(p)

    cid = "{:06}".format(bisect.bisect_right(Ps[p-1], y))

    print((pid+cid))

n, m = list(map(int, input().split()))
py = [list(map(int, input().split())) for _ in range(m)]
spy = sorted(py)
signate = {}
cnt = 0
last_p = 0
for p, y in spy:
    pref = "{:06}".format(p)
    if last_p == p:
        cnt += 1
    else:
        last_p = p
        cnt = 1
    year = "{:06}".format(cnt)
    signate["{}-{}".format(p, y)] = pref + year
for p, y in py:
    print((signate["{}-{}".format(p, y)]))

import bisect

n, m = list(map(int, input().split()))
Ps = [[] for _ in range(n)]
PY = []
for _ in range(m):
    p, y = list(map(int, input().split()))
    Ps[p - 1].append(y)
    PY.append((p, y))
for ls in Ps:
    ls.sort()
for p, y in PY:
    pid = "{:06}".format(p)
    cid = "{:06}".format(bisect.bisect_right(Ps[p - 1], y))
    print((pid + cid))

+import bisect + -py = [list(map(int, input().split())) for _ in range(m)] -spy = sorted(py) -signate = {} -cnt = 0 -last_p = 0 -for p, y in spy: -    pref = "{:06}".format(p) -    if last_p == p: -        cnt += 1 -    else: -        last_p = p -        cnt = 1 -    year = "{:06}".format(cnt) -    signate["{}-{}".format(p, y)] = pref + year -for p, y in py: -    print((signate["{}-{}".format(p, y)])) +Ps = [[] for _ in range(n)] +PY = [] +for _ in range(m): +    p, y = list(map(int, input().split())) +    Ps[p - 1].append(y) +    PY.append((p, y)) +for ls in Ps: +    ls.sort() +for p, y in PY: +    pid = "{:06}".format(p) +    cid = "{:06}".format(bisect.bisect_right(Ps[p - 1], y)) +    print((pid + cid))