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

p,y = [],[]

for i in range(m):

    v1,v2 = list(map(int,input().split()))

    p.append(v1)

    y.append(v2)

    

py = list(zip(p,y,list(range(m))))

py = sorted(py)

p,y,index = list(zip(*py))



ans = []

start = p[0]

count = 1

for i in range(m):

    if start == p[i]:

        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))

        count += 1

    else:

        count = 1

        start = p[i]

        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))

        count += 1



ans1 = list(zip(index,ans))

ans1 = sorted(ans1)

index,ans = list(zip(*ans1))

for i in ans:

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

p,y = [],[]

for i in range(m):

    v1,v2 = list(map(int,input().split()))

    p.append(v1)

    y.append(v2)

    

py = list(zip(p,y,list(range(m))))

py = sorted(py)

p,y,index = list(zip(*py))

 

ans = []

start = p[0]

count = 1

for i in range(m):

    if start == p[i]:

        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))

        count += 1

    else:

        count = 1

        start = p[i]

        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))

        count += 1

 

ans = list(zip(index,ans))

ans = sorted(ans)

index,ans = list(zip(*ans))

for i in ans:

    print(i)
n, m = list(map(int, input().split()))
p, y = [], []
for i in range(m):
    v1, v2 = list(map(int, input().split()))
    p.append(v1)
    y.append(v2)
py = list(zip(p, y, list(range(m))))
py = sorted(py)
p, y, index = list(zip(*py))
ans = []
start = p[0]
count = 1
for i in range(m):
    if start == p[i]:
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1
    else:
        count = 1
        start = p[i]
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1
ans1 = list(zip(index, ans))
ans1 = sorted(ans1)
index, ans = list(zip(*ans1))
for i in ans:
    print(i)

n, m = list(map(int, input().split()))
p, y = [], []
for i in range(m):
    v1, v2 = list(map(int, input().split()))
    p.append(v1)
    y.append(v2)
py = list(zip(p, y, list(range(m))))
py = sorted(py)
p, y, index = list(zip(*py))
ans = []
start = p[0]
count = 1
for i in range(m):
    if start == p[i]:
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1
    else:
        count = 1
        start = p[i]
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1
ans = list(zip(index, ans))
ans = sorted(ans)
index, ans = list(zip(*ans))
for i in ans:
    print(i)

-ans1 = list(zip(index, ans)) -ans1 = sorted(ans1) -index, ans = list(zip(*ans1)) +ans = list(zip(index, ans)) +ans = sorted(ans) +index, ans = list(zip(*ans))