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



prefectures = []

for i in range(m):

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

    prefectures.append({'i': i, 'p': p, 'y': y})



prefectures.sort(key=lambda x: (x['p'], x['y']))



ans = []

cnt = 1

for i in range(len(prefectures)):

    if i != 0:

        if prefectures[i-1]['p'] == prefectures[i]['p']:

            cnt += 1

        else:

            cnt = 1

    s = str(prefectures[i]['p']).zfill(6)+str(cnt).zfill(6)

    ans.append({'i': prefectures[i]['i'], 'p': s})





ans.sort(key=lambda x: x['i'])



for x in ans:

    print((x['p']))

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



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

for i in range(m):

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

    prefectures[p-1].append((y, i))



ans = [None] * m

for i, p in enumerate(prefectures):

    p.sort()

    for j, (y, k) in enumerate(p):

        ans[k] = "%06d%06d" % (i+1, j+1)



print(*ans, sep='\n')

n, m = list(map(int, input().split()))
prefectures = []
for i in range(m):
    p, y = list(map(int, input().split()))
    prefectures.append({"i": i, "p": p, "y": y})
prefectures.sort(key=lambda x: (x["p"], x["y"]))
ans = []
cnt = 1
for i in range(len(prefectures)):
    if i != 0:
        if prefectures[i - 1]["p"] == prefectures[i]["p"]:
            cnt += 1
        else:
            cnt = 1
    s = str(prefectures[i]["p"]).zfill(6) + str(cnt).zfill(6)
    ans.append({"i": prefectures[i]["i"], "p": s})
ans.sort(key=lambda x: x["i"])
for x in ans:
    print((x["p"]))

n, m = map(int, input().split())
prefectures = [[] for _ in range(n)]
for i in range(m):
    p, y = map(int, input().split())
    prefectures[p - 1].append((y, i))
ans = [None] * m
for i, p in enumerate(prefectures):
    p.sort()
    for j, (y, k) in enumerate(p):
        ans[k] = "%06d%06d" % (i + 1, j + 1)
print(*ans, sep="\n")

-n, m = list(map(int, input().split())) -prefectures = [] +n, m = map(int, input().split()) +prefectures = [[] for _ in range(n)] -    p, y = list(map(int, input().split())) -    prefectures.append({"i": i, "p": p, "y": y}) -prefectures.sort(key=lambda x: (x["p"], x["y"])) -ans = [] -cnt = 1 -for i in range(len(prefectures)): -    if i != 0: -        if prefectures[i - 1]["p"] == prefectures[i]["p"]: -            cnt += 1 -        else: -            cnt = 1 -    s = str(prefectures[i]["p"]).zfill(6) + str(cnt).zfill(6) -    ans.append({"i": prefectures[i]["i"], "p": s}) -ans.sort(key=lambda x: x["i"]) -for x in ans: -    print((x["p"])) +    p, y = map(int, input().split()) +    prefectures[p - 1].append((y, i)) +ans = [None] * m +for i, p in enumerate(prefectures): +    p.sort() +    for j, (y, k) in enumerate(p): +        ans[k] = "%06d%06d" % (i + 1, j + 1) +print(*ans, sep="\n")