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

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



PY.sort()



pnow = PY[0][0]

c = 1



ans = [-1 for i in range(M)]



for i in range(M):

    if pnow != PY[i][0]:

        c = 1

        pnow = PY[i][0]

    ans[PY[i][2]] = str(PY[i][0]).zfill(6) + str(c).zfill(6)

    c += 1



print(('\n'.join(ans)))

import sys

readline = sys.stdin.readline

sys.setrecursionlimit(10**8)

mod = 10**9+7

#mod = 998244353

INF = 10**18

eps = 10**-7



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



PY = [list(map(int,readline().split())) + [i] for i in range(M)]



PY.sort(key=lambda x: (x[0],x[1]))



ans = [None]*M

nowp = 1

cnt = 1

for i in range(M):

    if PY[i][0] != nowp:

        cnt = 1

        nowp = PY[i][0]

    ans[PY[i][2]] = [nowp,cnt]

    cnt += 1



for i in range(M):

    print((str(ans[i][0]).zfill(6) + str(ans[i][1]).zfill(6)))

N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort()
pnow = PY[0][0]
c = 1
ans = [-1 for i in range(M)]
for i in range(M):
    if pnow != PY[i][0]:
        c = 1
        pnow = PY[i][0]
    ans[PY[i][2]] = str(PY[i][0]).zfill(6) + str(c).zfill(6)
    c += 1
print(("\n".join(ans)))

import sys

readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
# mod = 998244353
INF = 10**18
eps = 10**-7
N, M = list(map(int, readline().split()))
PY = [list(map(int, readline().split())) + [i] for i in range(M)]
PY.sort(key=lambda x: (x[0], x[1]))
ans = [None] * M
nowp = 1
cnt = 1
for i in range(M):
    if PY[i][0] != nowp:
        cnt = 1
        nowp = PY[i][0]
    ans[PY[i][2]] = [nowp, cnt]
    cnt += 1
for i in range(M):
    print((str(ans[i][0]).zfill(6) + str(ans[i][1]).zfill(6)))

-N, M = list(map(int, input().split())) -PY = [list(map(int, input().split())) + [i] for i in range(M)] -PY.sort() -pnow = PY[0][0] -c = 1 -ans = [-1 for i in range(M)] +import sys + +readline = sys.stdin.readline +sys.setrecursionlimit(10**8) +mod = 10**9 + 7 +# mod = 998244353 +INF = 10**18 +eps = 10**-7 +N, M = list(map(int, readline().split())) +PY = [list(map(int, readline().split())) + [i] for i in range(M)] +PY.sort(key=lambda x: (x[0], x[1])) +ans = [None] * M +nowp = 1 +cnt = 1 -    if pnow != PY[i][0]: -        c = 1 -        pnow = PY[i][0] -    ans[PY[i][2]] = str(PY[i][0]).zfill(6) + str(c).zfill(6) -    c += 1 -print(("\n".join(ans))) +    if PY[i][0] != nowp: +        cnt = 1 +        nowp = PY[i][0] +    ans[PY[i][2]] = [nowp, cnt] +    cnt += 1 +for i in range(M): +    print((str(ans[i][0]).zfill(6) + str(ans[i][1]).zfill(6)))