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

pyi = []

exists = [0] * N

for i in range(M):

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

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

pyi.sort(key = lambda x: x[1])

iid = []

for i in range(M):

    p = pyi[i][0]

    div = pyi[i][2]

    exists[p - 1] += 1

    iid.append([div, str(p).zfill(6)+str(exists[p - 1]).zfill(6)])

iid.sort()

for i in range(M):

    print((iid[i][1]))
N, M = list(map(int, input().split()))

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

sPY = sorted(PY, key=lambda py: (py[0],py[1]))



i = 1

bp = 1

d = {}

for p, y in sPY:

    if p != bp:

        i = 1

        bp = p

    d[y] = i

    i += 1



for p, y in PY:

    print(("{0:06}{1:06}".format(p, d[y])))
N, M = list(map(int, input().split()))
pyi = []
exists = [0] * N
for i in range(M):
    p, y = list(map(int, input().split()))
    pyi.append([p, y, i])
pyi.sort(key=lambda x: x[1])
iid = []
for i in range(M):
    p = pyi[i][0]
    div = pyi[i][2]
    exists[p - 1] += 1
    iid.append([div, str(p).zfill(6) + str(exists[p - 1]).zfill(6)])
iid.sort()
for i in range(M):
    print((iid[i][1]))

N, M = list(map(int, input().split()))
PY = [tuple(map(int, input().split())) for _ in range(M)]
sPY = sorted(PY, key=lambda py: (py[0], py[1]))
i = 1
bp = 1
d = {}
for p, y in sPY:
    if p != bp:
        i = 1
        bp = p
    d[y] = i
    i += 1
for p, y in PY:
    print(("{0:06}{1:06}".format(p, d[y])))

-pyi = [] -exists = [0] * N -for i in range(M): -    p, y = list(map(int, input().split())) -    pyi.append([p, y, i]) -pyi.sort(key=lambda x: x[1]) -iid = [] -for i in range(M): -    p = pyi[i][0] -    div = pyi[i][2] -    exists[p - 1] += 1 -    iid.append([div, str(p).zfill(6) + str(exists[p - 1]).zfill(6)]) -iid.sort() -for i in range(M): -    print((iid[i][1])) +PY = [tuple(map(int, input().split())) for _ in range(M)] +sPY = sorted(PY, key=lambda py: (py[0], py[1])) +i = 1 +bp = 1 +d = {} +for p, y in sPY: +    if p != bp: +        i = 1 +        bp = p +    d[y] = i +    i += 1 +for p, y in PY: +    print(("{0:06}{1:06}".format(p, d[y])))