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

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

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

for i in range(m):

    p, y = list(map(int, input().split()))

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

buf = [None] * m

for p, l in enumerate(cnt):

    if not l:

        continue

    l.sort()

    for j, (y, i) in enumerate(l):

        buf[i] = '{:06d}{:06d}'.format(p, j + 1)

print(('\n'.join(buf)))
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)))

n, m = list(map(int, input().split()))
cnt = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = list(map(int, input().split()))
    cnt[p].append((y, i))
buf = [None] * m
for p, l in enumerate(cnt):
    if not l:
        continue
    l.sort()
    for j, (y, i) in enumerate(l):
        buf[i] = "{:06d}{:06d}".format(p, j + 1)
print(("\n".join(buf)))

-import collections -import bisect - -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))) +cnt = [[] for _ in range(n + 1)] +for i in range(m): +    p, y = list(map(int, input().split())) +    cnt[p].append((y, i)) +buf = [None] * m +for p, l in enumerate(cnt): +    if not l: +        continue +    l.sort() +    for j, (y, i) in enumerate(l): +        buf[i] = "{:06d}{:06d}".format(p, j + 1) +print(("\n".join(buf)))