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

C = [[i]+list(map(int,input().split())) for i in range(m)]

C.sort(key=lambda c:c[1:])

prev = 0

count = 0

for c in C:

    if prev==c[1]: count+=1

    else: count=1

    c.append(format(c[1],'0>6')+format(count,'0>6'))

    prev=c[1]



for c in sorted(C, key=lambda c:c[0]):

    print((c[3]))
#%%

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): # p自体を変えないことで、市の順番は保っておく

    a[x]+=[y] # 各県に対し、存在する生誕年を昇順でリスト化する。最初の1つはdefaultdictよりOK

for x,y in p: # 各市を1つずつ取得

    z=bisect.bisect(a[x],y) # bisectでindexを探索。bisect_rightに注意。

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

n, m = list(map(int, input().split()))
C = [[i] + list(map(int, input().split())) for i in range(m)]
C.sort(key=lambda c: c[1:])
prev = 0
count = 0
for c in C:
    if prev == c[1]:
        count += 1
    else:
        count = 1
    c.append(format(c[1], "0>6") + format(count, "0>6"))
    prev = c[1]
for c in sorted(C, key=lambda c: c[0]):
    print((c[3]))

#%%
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):  # p自体を変えないことで、市の順番は保っておく
    a[x] += [y]  # 各県に対し、存在する生誕年を昇順でリスト化する。最初の1つはdefaultdictよりOK
for x, y in p:  # 各市を1つずつ取得
    z = bisect.bisect(a[x], y)  # bisectでindexを探索。bisect_rightに注意。
    print(("%06d%06d" % (x, z)))

+#%% +import collections +import bisect + +#%% -C = [[i] + list(map(int, input().split())) for i in range(m)] -C.sort(key=lambda c: c[1:]) -prev = 0 -count = 0 -for c in C: -    if prev == c[1]: -        count += 1 -    else: -        count = 1 -    c.append(format(c[1], "0>6") + format(count, "0>6")) -    prev = c[1] -for c in sorted(C, key=lambda c: c[0]): -    print((c[3])) +p = [[int(j) for j in input().split()] for i in range(m)] +a = collections.defaultdict(list) +for x, y in sorted(p):  # p自体を変えないことで、市の順番は保っておく +    a[x] += [y]  # 各県に対し、存在する生誕年を昇順でリスト化する。最初の1つはdefaultdictよりOK +for x, y in p:  # 各市を1つずつ取得 +    z = bisect.bisect(a[x], y)  # bisectでindexを探索。bisect_rightに注意。 +    print(("%06d%06d" % (x, z)))