from operator import itemgetter

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

PY = sorted(((i, tuple(map(int, input().split()))) for i in range(M)), key=itemgetter(1))

L = []

prev, x = 0, 1

for i, (p, _y) in PY:

    if p == prev:

        x += 1

    else:

        prev = p

        x = 1

    L.append((i, "{:06d}{:06d}".format(p, x)))

L.sort()

print(*[l for _, l in L], sep="\n")

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

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

ans=[None]*M

I=sorted(list(range(M)),key=lambda i: PY[i][1])

C=[0]*(N+1)

for i in I:

    p=PY[i][0]

    C[p]+=1

    ans[i]=(p,C[p])

def f(x):

    s=str(x)

    return "0"*(6-len(s))+s

for p,c in ans:

    print((f(p)+f(c)))
from operator import itemgetter

N, M = map(int, input().split())
PY = sorted(
    ((i, tuple(map(int, input().split()))) for i in range(M)), key=itemgetter(1)
)
L = []
prev, x = 0, 1
for i, (p, _y) in PY:
    if p == prev:
        x += 1
    else:
        prev = p
        x = 1
    L.append((i, "{:06d}{:06d}".format(p, x)))
L.sort()
print(*[l for _, l in L], sep="\n")

N, M = list(map(int, input().split()))
PY = [tuple(map(int, input().split())) for _ in range(M)]
ans = [None] * M
I = sorted(list(range(M)), key=lambda i: PY[i][1])
C = [0] * (N + 1)
for i in I:
    p = PY[i][0]
    C[p] += 1
    ans[i] = (p, C[p])


def f(x):
    s = str(x)
    return "0" * (6 - len(s)) + s


for p, c in ans:
    print((f(p) + f(c)))

-from operator import itemgetter +N, M = list(map(int, input().split())) +PY = [tuple(map(int, input().split())) for _ in range(M)] +ans = [None] * M +I = sorted(list(range(M)), key=lambda i: PY[i][1]) +C = [0] * (N + 1) +for i in I: +    p = PY[i][0] +    C[p] += 1 +    ans[i] = (p, C[p]) -N, M = map(int, input().split()) -PY = sorted( -    ((i, tuple(map(int, input().split()))) for i in range(M)), key=itemgetter(1) -) -L = [] -prev, x = 0, 1 -for i, (p, _y) in PY: -    if p == prev: -        x += 1 -    else: -        prev = p -        x = 1 -    L.append((i, "{:06d}{:06d}".format(p, x))) -L.sort() -print(*[l for _, l in L], sep="\n") + +def f(x): +    s = str(x) +    return "0" * (6 - len(s)) + s + + +for p, c in ans: +    print((f(p) + f(c)))