from heapq import heappush, heappop

from collections import deque,defaultdict,Counter

import itertools

from itertools import permutations

import sys

import bisect

import string

sys.setrecursionlimit(10**6)

def SI():

    return input().split()

def MI():

    return list(map(int,input().split()))

def I():

    return int(eval(input()))

def LI():

    return [int(i) for i in input().split()]

YN=['Yes','No']

mo=10**9+7



n,m=MI()

pref=[]

for i in range(m):

    p,y=MI()

    pref+=[(p,i,y)]

pref.sort(key=lambda x:x[0]*10**10+x[2])

c=0

pre=pref[0][0]

ans=[]

for p,i,y in pref:

    pid='0'*(6-len(str(p)))+str(p)

    if pre==p:

        c+=1

        cid='0'*(6-len(str(c)))+str(c)

    else:

        c=1

        cid='0'*(6-len(str(c)))+str(c)

    ans+=[(i,pid+cid)]

    pre=p

ans.sort(key=lambda x:x[0])

for i,iid in ans:

    print(iid)

from heapq import heappush, heappop

from collections import deque,defaultdict,Counter

import itertools

from itertools import permutations

import sys

import bisect

import string

sys.setrecursionlimit(10**6)

def SI():

    return input().split()

def MI():

    return list(map(int,input().split()))

def I():

    return int(eval(input()))

def LI():

    return [int(i) for i in input().split()]

YN=['Yes','No']

mo=10**9+7



n,m=MI()

ids=[0]*m

pref=[[] for i in range(1+n)]

for i in range(m):

    p,y=MI()

    pref[p]+=[(i,y)]

for p in range(1,n+1):

    ls=pref[p]

    ls.sort(key=lambda x:x[1])

    c=1

    for i,y in ls:

        pid='0'*(6-len(str(p)))+str(p)

        cid='0'*(6-len(str(c)))+str(c)

        c+=1

        ids[i]=pid+cid

        

for iid in ids:

    print(iid)

from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations
import sys
import bisect
import string

sys.setrecursionlimit(10**6)


def SI():
    return input().split()


def MI():
    return list(map(int, input().split()))


def I():
    return int(eval(input()))


def LI():
    return [int(i) for i in input().split()]


YN = ["Yes", "No"]
mo = 10**9 + 7
n, m = MI()
pref = []
for i in range(m):
    p, y = MI()
    pref += [(p, i, y)]
pref.sort(key=lambda x: x[0] * 10**10 + x[2])
c = 0
pre = pref[0][0]
ans = []
for p, i, y in pref:
    pid = "0" * (6 - len(str(p))) + str(p)
    if pre == p:
        c += 1
        cid = "0" * (6 - len(str(c))) + str(c)
    else:
        c = 1
        cid = "0" * (6 - len(str(c))) + str(c)
    ans += [(i, pid + cid)]
    pre = p
ans.sort(key=lambda x: x[0])
for i, iid in ans:
    print(iid)

from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations
import sys
import bisect
import string

sys.setrecursionlimit(10**6)


def SI():
    return input().split()


def MI():
    return list(map(int, input().split()))


def I():
    return int(eval(input()))


def LI():
    return [int(i) for i in input().split()]


YN = ["Yes", "No"]
mo = 10**9 + 7
n, m = MI()
ids = [0] * m
pref = [[] for i in range(1 + n)]
for i in range(m):
    p, y = MI()
    pref[p] += [(i, y)]
for p in range(1, n + 1):
    ls = pref[p]
    ls.sort(key=lambda x: x[1])
    c = 1
    for i, y in ls:
        pid = "0" * (6 - len(str(p))) + str(p)
        cid = "0" * (6 - len(str(c))) + str(c)
        c += 1
        ids[i] = pid + cid
for iid in ids:
    print(iid)

-pref = [] +ids = [0] * m +pref = [[] for i in range(1 + n)] -    pref += [(p, i, y)] -pref.sort(key=lambda x: x[0] * 10**10 + x[2]) -c = 0 -pre = pref[0][0] -ans = [] -for p, i, y in pref: -    pid = "0" * (6 - len(str(p))) + str(p) -    if pre == p: +    pref[p] += [(i, y)] +for p in range(1, n + 1): +    ls = pref[p] +    ls.sort(key=lambda x: x[1]) +    c = 1 +    for i, y in ls: +        pid = "0" * (6 - len(str(p))) + str(p) +        cid = "0" * (6 - len(str(c))) + str(c) -        cid = "0" * (6 - len(str(c))) + str(c) -    else: -        c = 1 -        cid = "0" * (6 - len(str(c))) + str(c) -    ans += [(i, pid + cid)] -    pre = p -ans.sort(key=lambda x: x[0]) -for i, iid in ans: +        ids[i] = pid + cid +for iid in ids: