I=lambda:list(map(int,input().split()));n,m=I();l=[[]for _ in[0]*-~n];a=[]

for i in range(m):p,y=I();l[p].append([y,i])

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

 for i,t in enumerate(sorted(l[p])):a.append([t[1],'%06d'%p+'%06d'%-~i])

for t in sorted(a):print((t[1]))
I=lambda:list(map(int,input().split()));n,m=I();l=[I()+[i]for i in range(m)];c=[0]*-~n;a=[0]*m

for p,y,i in sorted(l,key=lambda x:x[1]):c[p]+=1;a[i]='%06d'%p+'%06d'%c[p]

for t in a:print(t)
I = lambda: list(map(int, input().split()))
n, m = I()
l = [[] for _ in [0] * -~n]
a = []
for i in range(m):
    p, y = I()
    l[p].append([y, i])
for p in range(1, n + 1):
    for i, t in enumerate(sorted(l[p])):
        a.append([t[1], "%06d" % p + "%06d" % -~i])
for t in sorted(a):
    print((t[1]))

I = lambda: list(map(int, input().split()))
n, m = I()
l = [I() + [i] for i in range(m)]
c = [0] * -~n
a = [0] * m
for p, y, i in sorted(l, key=lambda x: x[1]):
    c[p] += 1
    a[i] = "%06d" % p + "%06d" % c[p]
for t in a:
    print(t)

-l = [[] for _ in [0] * -~n] -a = [] -for i in range(m): -    p, y = I() -    l[p].append([y, i]) -for p in range(1, n + 1): -    for i, t in enumerate(sorted(l[p])): -        a.append([t[1], "%06d" % p + "%06d" % -~i]) -for t in sorted(a): -    print((t[1])) +l = [I() + [i] for i in range(m)] +c = [0] * -~n +a = [0] * m +for p, y, i in sorted(l, key=lambda x: x[1]): +    c[p] += 1 +    a[i] = "%06d" % p + "%06d" % c[p] +for t in a: +    print(t)