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

ans = [""] * m

li = []

for i in range(m):

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

    li.append((p, y, i))

li.sort()

cnt = 1

ans[li[0][2]] = "{:06}{:06}".format(li[0][0], cnt)

for i in range(1, m):

    cnt = cnt + 1 if li[i - 1][0] == li[i][0] else 1

    ans[li[i][2]] = "{:06}{:06}".format(li[i][0], cnt)

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

import sys

readline = sys.stdin.readline

from collections import defaultdict

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

ans = [""] * m

li = []

for i in range(m):

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

    li.append((p, y, i))

li.sort()

cnt = 1

ans[li[0][2]] = "{:06}{:06}".format(li[0][0], cnt)

for i in range(1, m):

    cnt = cnt + 1 if li[i - 1][0] == li[i][0] else 1

    ans[li[i][2]] = "{:06}{:06}".format(li[i][0], cnt)

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

n, m = map(int, input().split())
ans = [""] * m
li = []
for i in range(m):
    p, y = map(int, input().split())
    li.append((p, y, i))
li.sort()
cnt = 1
ans[li[0][2]] = "{:06}{:06}".format(li[0][0], cnt)
for i in range(1, m):
    cnt = cnt + 1 if li[i - 1][0] == li[i][0] else 1
    ans[li[i][2]] = "{:06}{:06}".format(li[i][0], cnt)
print(*ans, sep="\n")

import sys

readline = sys.stdin.readline
from collections import defaultdict

n, m = map(int, input().split())
ans = [""] * m
li = []
for i in range(m):
    p, y = map(int, readline().split())
    li.append((p, y, i))
li.sort()
cnt = 1
ans[li[0][2]] = "{:06}{:06}".format(li[0][0], cnt)
for i in range(1, m):
    cnt = cnt + 1 if li[i - 1][0] == li[i][0] else 1
    ans[li[i][2]] = "{:06}{:06}".format(li[i][0], cnt)
print(*ans, sep="\n")

+import sys + +readline = sys.stdin.readline +from collections import defaultdict + -    p, y = map(int, input().split()) +    p, y = map(int, readline().split())