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

dt=[]

for i in range(n):

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

    dt+=[[i,p,y,0]]

dt.sort(key=lambda x:(x[1],x[2]))

pi=1

prep=0

for x in dt:

    if prep==x[1]:

        pi+=1

    else:

        pi=1

    x[3]=pi

    prep=x[1]

dt.sort()

for x in dt:

    print((str(x[1]).zfill(6)+str(x[3]).zfill(6)))
import sys

input=sys.stdin.readline



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

dt=[]

for i in range(n):

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

    dt+=[[i,p,y,0]]

dt.sort(key=lambda x:(x[1],x[2]))

pi=1

prep=0

for x in dt:

    if prep==x[1]:

        pi+=1

    else:

        pi=1

    x[3]=pi

    prep=x[1]

dt.sort()

for x in dt:

    print((str(x[1]).zfill(6)+str(x[3]).zfill(6)))
m, n = list(map(int, input().split()))
dt = []
for i in range(n):
    p, y = list(map(int, input().split()))
    dt += [[i, p, y, 0]]
dt.sort(key=lambda x: (x[1], x[2]))
pi = 1
prep = 0
for x in dt:
    if prep == x[1]:
        pi += 1
    else:
        pi = 1
    x[3] = pi
    prep = x[1]
dt.sort()
for x in dt:
    print((str(x[1]).zfill(6) + str(x[3]).zfill(6)))

import sys

input = sys.stdin.readline
m, n = list(map(int, input().split()))
dt = []
for i in range(n):
    p, y = list(map(int, input().split()))
    dt += [[i, p, y, 0]]
dt.sort(key=lambda x: (x[1], x[2]))
pi = 1
prep = 0
for x in dt:
    if prep == x[1]:
        pi += 1
    else:
        pi = 1
    x[3] = pi
    prep = x[1]
dt.sort()
for x in dt:
    print((str(x[1]).zfill(6) + str(x[3]).zfill(6)))

+import sys + +input = sys.stdin.readline