import bisect

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



prefs_list = []

prefs_dict = {}

for i in range(m):

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

  prefs_list.append([p,y])

  if p in prefs_dict:

    prefs_dict[p].append(y)

  else:

    prefs_dict[p] = [y]



for key in prefs_dict:

  prefs_dict[key].sort()







for pref in prefs_list:

  print((str(pref[0]).zfill(6) + str(bisect.bisect_left(prefs_dict[pref[0]], pref[1])+1).zfill(6)))

from collections import defaultdict

import bisect



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

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



prefs = defaultdict(list)





for p, y in PY:

    # ここで実際の誕生年をつめてから、あとで県ごとにソートして単なる順番に座標圧縮

    prefs[p].append(y)



for k in list(prefs.keys()):

    # 順に並び替えたので、後にbisectで位置を探せば誕生年から順番で取り出せる

    prefs[k].sort()



for p, y in PY:

    idx = bisect.bisect_left(prefs[p], y)

    print((str(p).zfill(6) + str(idx+1).zfill(6)))
import bisect

n, m = list(map(int, input().split()))
prefs_list = []
prefs_dict = {}
for i in range(m):
    p, y = list(map(int, input().split()))
    prefs_list.append([p, y])
    if p in prefs_dict:
        prefs_dict[p].append(y)
    else:
        prefs_dict[p] = [y]
for key in prefs_dict:
    prefs_dict[key].sort()
for pref in prefs_list:
    print(
        (
            str(pref[0]).zfill(6)
            + str(bisect.bisect_left(prefs_dict[pref[0]], pref[1]) + 1).zfill(6)
        )
    )

from collections import defaultdict
import bisect

N, M = list(map(int, input().split()))
PY = [tuple(map(int, input().split())) for _ in range(M)]
prefs = defaultdict(list)
for p, y in PY:
    # ここで実際の誕生年をつめてから、あとで県ごとにソートして単なる順番に座標圧縮
    prefs[p].append(y)
for k in list(prefs.keys()):
    # 順に並び替えたので、後にbisectで位置を探せば誕生年から順番で取り出せる
    prefs[k].sort()
for p, y in PY:
    idx = bisect.bisect_left(prefs[p], y)
    print((str(p).zfill(6) + str(idx + 1).zfill(6)))

+from collections import defaultdict -n, m = list(map(int, input().split())) -prefs_list = [] -prefs_dict = {} -for i in range(m): -    p, y = list(map(int, input().split())) -    prefs_list.append([p, y]) -    if p in prefs_dict: -        prefs_dict[p].append(y) -    else: -        prefs_dict[p] = [y] -for key in prefs_dict: -    prefs_dict[key].sort() -for pref in prefs_list: -    print( -        ( -            str(pref[0]).zfill(6) -            + str(bisect.bisect_left(prefs_dict[pref[0]], pref[1]) + 1).zfill(6) -        ) -    ) +N, M = list(map(int, input().split())) +PY = [tuple(map(int, input().split())) for _ in range(M)] +prefs = defaultdict(list) +for p, y in PY: +    # ここで実際の誕生年をつめてから、あとで県ごとにソートして単なる順番に座標圧縮 +    prefs[p].append(y) +for k in list(prefs.keys()): +    # 順に並び替えたので、後にbisectで位置を探せば誕生年から順番で取り出せる +    prefs[k].sort() +for p, y in PY: +    idx = bisect.bisect_left(prefs[p], y) +    print((str(p).zfill(6) + str(idx + 1).zfill(6)))