import sys

f=lambda:list(map(int,sys.stdin.readline().split()))

n,m=f()

lt=[]

for i in range(m):

  p,y=f()

  lt+=[(p,y,i)]

lt.sort()

d={}

t=c=0

for p,y,i in lt:

  if p>t: t,c=p,1

  else: c+=1

  d[i]=str(p).zfill(6)+str(c).zfill(6)

for _,v in sorted(d.items()): print(v)
import sys

f=lambda:list(map(int,sys.stdin.readline().split()))

_,m=f()

d,t,c={},0,0

for p,y,i in sorted(list(f())+[i] for i in range(m)):

  if p>t: t,c=p,1

  else: c+=1

  d[i]=str(p).zfill(6)+str(c).zfill(6)

for _,v in sorted(d.items()): print(v)
import sys

f = lambda: list(map(int, sys.stdin.readline().split()))
n, m = f()
lt = []
for i in range(m):
    p, y = f()
    lt += [(p, y, i)]
lt.sort()
d = {}
t = c = 0
for p, y, i in lt:
    if p > t:
        t, c = p, 1
    else:
        c += 1
    d[i] = str(p).zfill(6) + str(c).zfill(6)
for _, v in sorted(d.items()):
    print(v)

import sys

f = lambda: list(map(int, sys.stdin.readline().split()))
_, m = f()
d, t, c = {}, 0, 0
for p, y, i in sorted(list(f()) + [i] for i in range(m)):
    if p > t:
        t, c = p, 1
    else:
        c += 1
    d[i] = str(p).zfill(6) + str(c).zfill(6)
for _, v in sorted(d.items()):
    print(v)

-n, m = f() -lt = [] -for i in range(m): -    p, y = f() -    lt += [(p, y, i)] -lt.sort() -d = {} -t = c = 0 -for p, y, i in lt: +_, m = f() +d, t, c = {}, 0, 0 +for p, y, i in sorted(list(f()) + [i] for i in range(m)):