from collections import*

import sys

input=sys.stdin.readline



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

d=defaultdict(list)

l=[]

for i in range(m):

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

    l.append([p,y])

    d[p].append(y)



for k,v in list(d.items()):

    d[k]=list(enumerate(sorted(v)))

d2=defaultdict(int)

for k,v in list(d.items()):

    for s,t in v:

        d2[(k,t)]=s+1

for i in l:

    print((str(i[0]).zfill(6)+str(d2[tuple(i)]).zfill(6)))
#from numpy import*

#from scipy import*

from collections import* #defaultdict Counter deque

from fractions import gcd

from functools import* #reduce

from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2)

from operator import mul

from bisect import* #bisect_left bisect_right

from heapq import* #heapify heappop heappushpop

from math import factorial

from copy import deepcopy

import sys

input=sys.stdin.readline

sys.setrecursionlimit(10**6)



#enumerate input



def main():

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

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

    py=sorted(sorted(py,key=lambda x:x[1]),key=lambda x:x[0])

    d=defaultdict(list)

    pre=py[0][0]

    num=1

    for p,_,i in py:

        if p==pre:

            d[i]=[p,num]

            num+=1

        else:

            num=2

            pre=p

            d[i]=[p,1]

#    print(d)

    for i in range(m):

        s,t=d[i]

        print((str(s).zfill(6)+str(t).zfill(6)))



    

if __name__ == '__main__':

    main()
from collections import *
import sys

input = sys.stdin.readline
n, m = list(map(int, input().split()))
d = defaultdict(list)
l = []
for i in range(m):
    p, y = list(map(int, input().split()))
    l.append([p, y])
    d[p].append(y)
for k, v in list(d.items()):
    d[k] = list(enumerate(sorted(v)))
d2 = defaultdict(int)
for k, v in list(d.items()):
    for s, t in v:
        d2[(k, t)] = s + 1
for i in l:
    print((str(i[0]).zfill(6) + str(d2[tuple(i)]).zfill(6)))

# from numpy import*
# from scipy import*
from collections import *  # defaultdict Counter deque
from fractions import gcd
from functools import *  # reduce
from itertools import *  # permutations("AB",repeat=2) combinations("AB",2) product("AB",2)
from operator import mul
from bisect import *  # bisect_left bisect_right
from heapq import *  # heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# enumerate input
def main():
    n, m = list(map(int, input().split()))
    py = [list(map(int, input().split())) + [i] for i in range(m)]
    py = sorted(sorted(py, key=lambda x: x[1]), key=lambda x: x[0])
    d = defaultdict(list)
    pre = py[0][0]
    num = 1
    for p, _, i in py:
        if p == pre:
            d[i] = [p, num]
            num += 1
        else:
            num = 2
            pre = p
            d[i] = [p, 1]
    #    print(d)
    for i in range(m):
        s, t = d[i]
        print((str(s).zfill(6) + str(t).zfill(6)))


if __name__ == "__main__":
    main()

-from collections import * +# from numpy import* +# from scipy import* +from collections import *  # defaultdict Counter deque +from fractions import gcd +from functools import *  # reduce +from itertools import *  # permutations("AB",repeat=2) combinations("AB",2) product("AB",2) +from operator import mul +from bisect import *  # bisect_left bisect_right +from heapq import *  # heapify heappop heappushpop +from math import factorial +from copy import deepcopy -n, m = list(map(int, input().split())) -d = defaultdict(list) -l = [] -for i in range(m): -    p, y = list(map(int, input().split())) -    l.append([p, y]) -    d[p].append(y) -for k, v in list(d.items()): -    d[k] = list(enumerate(sorted(v))) -d2 = defaultdict(int) -for k, v in list(d.items()): -    for s, t in v: -        d2[(k, t)] = s + 1 -for i in l: -    print((str(i[0]).zfill(6) + str(d2[tuple(i)]).zfill(6))) +sys.setrecursionlimit(10**6) +# enumerate input +def main(): +    n, m = list(map(int, input().split())) +    py = [list(map(int, input().split())) + [i] for i in range(m)] +    py = sorted(sorted(py, key=lambda x: x[1]), key=lambda x: x[0]) +    d = defaultdict(list) +    pre = py[0][0] +    num = 1 +    for p, _, i in py: +        if p == pre: +            d[i] = [p, num] +            num += 1 +        else: +            num = 2 +            pre = p +            d[i] = [p, 1] +    #    print(d) +    for i in range(m): +        s, t = d[i] +        print((str(s).zfill(6) + str(t).zfill(6))) + + +if __name__ == "__main__": +    main()