from collections import defaultdict

N, M = list(map(int, input().split()))

l = []

for i in range(M):

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

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



l.sort()

d = defaultdict(int)



c = []

for y, p, i in l:

  d[p] += 1

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

  

c.sort()

for i, x in c:

  print(x)
from collections import defaultdict

N, M = list(map(int, input().split()))

l = [list(map(int, input().split())) for _ in range(M)]



d = defaultdict(int)

c = {}

for p, y in sorted(l, key=lambda x: x[1]):

  d[p] += 1

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



for p, y in l:

  print((c[y]))
from collections import defaultdict

N, M = list(map(int, input().split()))
l = []
for i in range(M):
    p, y = list(map(int, input().split()))
    l.append((y, p, i))
l.sort()
d = defaultdict(int)
c = []
for y, p, i in l:
    d[p] += 1
    c.append((i, str(p).zfill(6) + str(d[p]).zfill(6)))
c.sort()
for i, x in c:
    print(x)

from collections import defaultdict

N, M = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(M)]
d = defaultdict(int)
c = {}
for p, y in sorted(l, key=lambda x: x[1]):
    d[p] += 1
    c[y] = str(p).zfill(6) + str(d[p]).zfill(6)
for p, y in l:
    print((c[y]))

-l = [] -for i in range(M): -    p, y = list(map(int, input().split())) -    l.append((y, p, i)) -l.sort() +l = [list(map(int, input().split())) for _ in range(M)] -c = [] -for y, p, i in l: +c = {} +for p, y in sorted(l, key=lambda x: x[1]): -    c.append((i, str(p).zfill(6) + str(d[p]).zfill(6))) -c.sort() -for i, x in c: -    print(x) +    c[y] = str(p).zfill(6) + str(d[p]).zfill(6) +for p, y in l: +    print((c[y]))