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

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



cs = [[] for i in range(N+1)]

for i,(p,y) in enumerate(src):

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



ans = [None]*M

for pi,cities in enumerate(cs):

    for order,(y,i) in enumerate(sorted(cities)):

        ans[i] = str(pi).zfill(6) + str(order+1).zfill(6)

print(*ans, sep='\n')

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

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



cs = [[] for i in range(N+1)]

for i,(p,y) in enumerate(src):

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

for cc in cs:

    cc.sort()



ans = [None] * M

for p in range(len(cs)):

    for i,(_,j) in enumerate(cs[p]):

        s = str(p).zfill(6) + str(i+1).zfill(6)

        ans[j] = s

print(*ans, sep='\n')

N, M = map(int, input().split())
src = [tuple(map(int, input().split())) for i in range(M)]
cs = [[] for i in range(N + 1)]
for i, (p, y) in enumerate(src):
    cs[p].append((y, i))
ans = [None] * M
for pi, cities in enumerate(cs):
    for order, (y, i) in enumerate(sorted(cities)):
        ans[i] = str(pi).zfill(6) + str(order + 1).zfill(6)
print(*ans, sep="\n")

N, M = map(int, input().split())
src = [tuple(map(int, input().split())) for i in range(M)]
cs = [[] for i in range(N + 1)]
for i, (p, y) in enumerate(src):
    cs[p].append((y, i))
for cc in cs:
    cc.sort()
ans = [None] * M
for p in range(len(cs)):
    for i, (_, j) in enumerate(cs[p]):
        s = str(p).zfill(6) + str(i + 1).zfill(6)
        ans[j] = s
print(*ans, sep="\n")

+for cc in cs: +    cc.sort() -for pi, cities in enumerate(cs): -    for order, (y, i) in enumerate(sorted(cities)): -        ans[i] = str(pi).zfill(6) + str(order + 1).zfill(6) +for p in range(len(cs)): +    for i, (_, j) in enumerate(cs[p]): +        s = str(p).zfill(6) + str(i + 1).zfill(6) +        ans[j] = s