# coding: utf-8

# N : 県の数, M: 市の数

import bisect



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

ps, ys = [], []



v = [ [] for _ in range(N+1) ]



for i in range(M):

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

    ps += [p]; ys += [y];

    v[p].append(y)



for i in range(N):

    v[i+1].sort()





for i in range(M):

    print("{:06d}".format(ps[i]), end="")

    print("{:06d}".format(bisect.bisect_left(v[ps[i]], ys[i])+1))

from bisect import bisect_left



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

P, Y = [], []

v = [[] for _ in range(N+1)]



for i in range(M):

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

    P += [p]

    Y += [y]

    v[p] += [y]



for i in range(N+1):

    v[i].sort()



for x, y in zip(P, Y):

    print ("%06d" % x, end = "")

    print ("%06d" % int(bisect_left(v[x], y) + 1))

# coding: utf-8
# N : 県の数, M: 市の数
import bisect

N, M = map(int, input().split())
ps, ys = [], []
v = [[] for _ in range(N + 1)]
for i in range(M):
    p, y = map(int, input().split())
    ps += [p]
    ys += [y]
    v[p].append(y)
for i in range(N):
    v[i + 1].sort()
for i in range(M):
    print("{:06d}".format(ps[i]), end="")
    print("{:06d}".format(bisect.bisect_left(v[ps[i]], ys[i]) + 1))

from bisect import bisect_left

N, M = map(int, input().split())
P, Y = [], []
v = [[] for _ in range(N + 1)]
for i in range(M):
    p, y = map(int, input().split())
    P += [p]
    Y += [y]
    v[p] += [y]
for i in range(N + 1):
    v[i].sort()
for x, y in zip(P, Y):
    print("%06d" % x, end="")
    print("%06d" % int(bisect_left(v[x], y) + 1))

-# coding: utf-8 -# N : 県の数, M: 市の数 -import bisect +from bisect import bisect_left -ps, ys = [], [] +P, Y = [], [] -    ps += [p] -    ys += [y] -    v[p].append(y) -for i in range(N): -    v[i + 1].sort() -for i in range(M): -    print("{:06d}".format(ps[i]), end="") -    print("{:06d}".format(bisect.bisect_left(v[ps[i]], ys[i]) + 1)) +    P += [p] +    Y += [y] +    v[p] += [y] +for i in range(N + 1): +    v[i].sort() +for x, y in zip(P, Y): +    print("%06d" % x, end="") +    print("%06d" % int(bisect_left(v[x], y) + 1))