import collections

import bisect



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

a=collections.defaultdict(list)

p=[[int(j) for j in input().split()] for i in range(m)]

for x,y in sorted(p):

  a[x]+=[y]

for x,y in p:

  z=bisect.bisect(a[x],y)

  print(("%06d%06d"%(x,z)))
import collections

import bisect



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

p=[[int(j) for j in input().split()] for i in range(m)]

a=collections.defaultdict(list)



for x,y in sorted(p):

  a[x]+=[y]

for x,y in p:

  z=bisect.bisect(a[x],y)

  print(("%06d%06d"%(x,z)))
import collections
import bisect

n, m = list(map(int, input().split()))
a = collections.defaultdict(list)
p = [[int(j) for j in input().split()] for i in range(m)]
for x, y in sorted(p):
    a[x] += [y]
for x, y in p:
    z = bisect.bisect(a[x], y)
    print(("%06d%06d" % (x, z)))

import collections
import bisect

n, m = list(map(int, input().split()))
p = [[int(j) for j in input().split()] for i in range(m)]
a = collections.defaultdict(list)
for x, y in sorted(p):
    a[x] += [y]
for x, y in p:
    z = bisect.bisect(a[x], y)
    print(("%06d%06d" % (x, z)))

+p = [[int(j) for j in input().split()] for i in range(m)] -p = [[int(j) for j in input().split()] for i in range(m)]