s=input().split()

n=int(s[0])

m=int(s[1])

l=[[] for i in range(100000)]

d=[{} for i in range(100000)]

inp=[]

for i in range(m):

    s=input().split()

    p=int(s[0])

    y=int(s[1])

    inp.append((p,y))

    l[p-1].append(y)

for i in range(100000):

    l[i].sort()

for i in range(100000):

    cnt=1

    for j in l[i]:

        d[i][j]=cnt

        cnt+=1

for pa in inp:

    L=pa[0]

    R=d[L-1][pa[1]]

    L=str(L)

    R=str(R)

    for i in range(6-len(L)):

        print("0",end="")

    print(L,end="")

    for i in range(6-len(R)):

        print("0",end="")

    print(R)

s=input().split()

n,m=int(s[0]),int(s[1])

l=[[] for i in range(100001)]

d=[{} for i in range(100001)]

inp=[]

for i in range(m):

    s=input().split()

    p,y=int(s[0]),int(s[1])

    inp.append((p,y))

    l[p].append(y)

for i in range(100001):

    l[i].sort()

for i in range(100001):

    cnt=1

    for j in l[i]:

        d[i][j]=cnt

        cnt+=1

for pa in inp:

    print((str(pa[0]).zfill(6)+str(d[pa[0]][pa[1]]).zfill(6)))
s = input().split()
n = int(s[0])
m = int(s[1])
l = [[] for i in range(100000)]
d = [{} for i in range(100000)]
inp = []
for i in range(m):
    s = input().split()
    p = int(s[0])
    y = int(s[1])
    inp.append((p, y))
    l[p - 1].append(y)
for i in range(100000):
    l[i].sort()
for i in range(100000):
    cnt = 1
    for j in l[i]:
        d[i][j] = cnt
        cnt += 1
for pa in inp:
    L = pa[0]
    R = d[L - 1][pa[1]]
    L = str(L)
    R = str(R)
    for i in range(6 - len(L)):
        print("0", end="")
    print(L, end="")
    for i in range(6 - len(R)):
        print("0", end="")
    print(R)

s = input().split()
n, m = int(s[0]), int(s[1])
l = [[] for i in range(100001)]
d = [{} for i in range(100001)]
inp = []
for i in range(m):
    s = input().split()
    p, y = int(s[0]), int(s[1])
    inp.append((p, y))
    l[p].append(y)
for i in range(100001):
    l[i].sort()
for i in range(100001):
    cnt = 1
    for j in l[i]:
        d[i][j] = cnt
        cnt += 1
for pa in inp:
    print((str(pa[0]).zfill(6) + str(d[pa[0]][pa[1]]).zfill(6)))

-n = int(s[0]) -m = int(s[1]) -l = [[] for i in range(100000)] -d = [{} for i in range(100000)] +n, m = int(s[0]), int(s[1]) +l = [[] for i in range(100001)] +d = [{} for i in range(100001)] -    p = int(s[0]) -    y = int(s[1]) +    p, y = int(s[0]), int(s[1]) -    l[p - 1].append(y) -for i in range(100000): +    l[p].append(y) +for i in range(100001): -for i in range(100000): +for i in range(100001): -    L = pa[0] -    R = d[L - 1][pa[1]] -    L = str(L) -    R = str(R) -    for i in range(6 - len(L)): -        print("0", end="") -    print(L, end="") -    for i in range(6 - len(R)): -        print("0", end="") -    print(R) +    print((str(pa[0]).zfill(6) + str(d[pa[0]][pa[1]]).zfill(6)))