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

ta=[list(map(int,input().split()))+[i] for i in range(m)]

a=sorted(ta)

ans=[-1]*m

j=0

for i in range(m):

    if j!=a[i][0]:

        j=a[i][0]

        k=1

    p=str(a[i][0]).zfill(6)+str(k).zfill(6)

    ans[a[i][2]]=p

    k+=1



a.sort()

for i in range(m):

    print((ans[i]))

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

x=[[] for _ in range(n+1)]

ans=[-1]*m

for i in range(m):

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

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



for p in range(1,n+1):

    x[p].sort()

    for j in range(len(x[p])):

        ans[x[p][j][1]]=str(p).zfill(6)+str(j+1).zfill(6)



for i in range(m):

    print((ans[i]))
_, m = list(map(int, input().split()))
ta = [list(map(int, input().split())) + [i] for i in range(m)]
a = sorted(ta)
ans = [-1] * m
j = 0
for i in range(m):
    if j != a[i][0]:
        j = a[i][0]
        k = 1
    p = str(a[i][0]).zfill(6) + str(k).zfill(6)
    ans[a[i][2]] = p
    k += 1
a.sort()
for i in range(m):
    print((ans[i]))

n, m = list(map(int, input().split()))
x = [[] for _ in range(n + 1)]
ans = [-1] * m
for i in range(m):
    p, y = list(map(int, input().split()))
    x[p].append([y, i])
for p in range(1, n + 1):
    x[p].sort()
    for j in range(len(x[p])):
        ans[x[p][j][1]] = str(p).zfill(6) + str(j + 1).zfill(6)
for i in range(m):
    print((ans[i]))

-_, m = list(map(int, input().split())) -ta = [list(map(int, input().split())) + [i] for i in range(m)] -a = sorted(ta) +n, m = list(map(int, input().split())) +x = [[] for _ in range(n + 1)] -j = 0 -    if j != a[i][0]: -        j = a[i][0] -        k = 1 -    p = str(a[i][0]).zfill(6) + str(k).zfill(6) -    ans[a[i][2]] = p -    k += 1 -a.sort() +    p, y = list(map(int, input().split())) +    x[p].append([y, i]) +for p in range(1, n + 1): +    x[p].sort() +    for j in range(len(x[p])): +        ans[x[p][j][1]] = str(p).zfill(6) + str(j + 1).zfill(6)