I=lambda:list(map(int,input().split()))

n,m=I()

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

for i in range(m):

  p,y=I()

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

a=[]

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

  l[p].sort()

  for i,t in enumerate(l[p]):

    a.append([t[1],'%06d'%p+'%06d'%-~i])

a.sort()

for t in a:

  print((t[1]))
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 = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = I()
    l[p].append([y, i])
a = []
for p in range(1, n + 1):
    l[p].sort()
    for i, t in enumerate(l[p]):
        a.append([t[1], "%06d" % p + "%06d" % -~i])
a.sort()
for t in a:
    print((t[1]))

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]))

-l = [[] for _ in range(n + 1)] +l = [[] for _ in [0] * -~n] +a = [] -a = [] -    l[p].sort() -    for i, t in enumerate(l[p]): +    for i, t in enumerate(sorted(l[p])): -a.sort() -for t in a: +for t in sorted(a):