from __future__ import print_function
import numpy as np
import sys
import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy,functools
from dataclasses import dataclass, field
from typing import Any
import heapq
from heapq import heappush
from heapq import heappop
# from Queue import PriorityQueue

# from itertools import accumulate
# from collections import deque
import random


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

n,m = map(int, input().split())
p=np.zeros(m+1,dtype=int)
y=np.zeros(m+1,dtype=int)
for i in range(1,m+1):
    p[i],y[i] = map(int, input().split())

# l=[]
# for i in range(1,n+1):
#     l.append(PriorityQueue())

# for i in range(1,n+1):
#     q.put((i,p[i]))
# eprint("=======================")
# heapl=[y[i] for i in range(1,m+1)]
# heapq.heapify(heapl)
# for i in range(1,m+1):
#     eprint(heapq.heappop(heapl))



# eprint("=======================")
l_pref=[[] for _ in range(n+1)]    # 県の数(==n)だけ空リストを用意
for i in range(1,m+1):
    heappush(l_pref[p[i]],(y[i],i))
    # eprint(l_pref[p[i]])

# eprint(l_pref)

# eprint("=======================")
# dict={}
# for ll in l_pref:
#     i=1
#     for xx in ll:
#         dict[xx]=i
#         i+=1
# print(dict)

# eprint("=======================")
# for i in range(1,n+1):
#     eprint(l_pref[i])

# heappush(heapl2,(p[i],y[i]))

# eprint("=======================")

# const = np.zeros(n+1,dtype=int)
# for i in range(1,n+1):
#     const[i] = len(l_pref[i])
#     eprint(str(const[i]) +" "+  str(l_pref[i]))



# eprint("=======================")
# for i in range(1,m+1):
#     eprint(str(p[i]) + " " + str( l_pref[p[i]].index((y[i],i))  + 1 ) )
# eprint("=======================")
for i in range(1,m+1):
    print("0"*(6-len(str(p[i])))  +  str(p[i])  +  "0"*(6-len(str( l_pref[p[i]].index((y[i],i))  + 1 ))) + str(l_pref[p[i]].index((y[i],i))  + 1) )


# eprint("=======================")


# for i in range(1,m+1):
#     eprint(str(p[i])+" "+" " + str(heappop(l_pref[p[i]])))
# eprint("=======================")

# for i in range(1,m+1):
#     print("0"*(6-len(str(p[i]))) + str(p[i]) + "0"*(6-len(str(const[p[i]] - len(l_pref[p[i]])+1))) + str( heappop( l_pref[p[i]] ) ) )



# l = []
# for i in range(1,n+1):
#     l[i] =

# i -> p[i] -> vector[i]
# vector[i] += 1
# print(p[i],vector[ p[i] ] )


# heappush(heap, 6)
# heappush(heap, 5)
# heappush(heap, 4)
# heappush(heap, 3)
# heappush(heap, 2)
# heappush(heap, 1)
# heappush(heap, 0)


# for i in range(1,n+1):


# for i in range(1,n+1):
#     dict[i] = p[i]


# 市			i 	{0,1, ...,(n-1) }
# 県			  	{0,1, ...{m-1}}
# それぞれの市の所属県	p_{i}	{p_0, p_1, p_2, ..., p_(n-1)}
# それぞれの市の設立年	y_{i}	{y_0, y_1, y_2, ..., y_{n-1}}


### FIXED CODE ###

from __future__ import print_function
# import numpy as np
import sys
import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy,functools
import heapq
from heapq import heappush
from heapq import heappop
import random


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

n,m = map(int, input().split())
p=[i for i in range(m+1)]
y=[i for i in range(m+1)]
for i in range(1,m+1):
    p[i],y[i] = map(int, input().split())


l_pref=[[] for _ in range(n+1)]    # 県の数(==n)だけ空リストを用意
for i in range(1,m+1):
    l_pref[p[i]].append((y[i],i))
for i in range(1,n+1):
    l_pref[i].sort()

# eprint(l_pref)


lll = [(1,1) for i in range(m+1)]
for i in range(1,n+1):
    for j in range(len(l_pref[i])):
        lll[l_pref[i][j][1]] = j+1
# eprint(lll)

for i in range(1,m+1):
    # temp =  l_pref[p[i]].index((y[i],i))  + 1
    print("0"*(6-len(str(p[i])))  +  str(p[i])  +  "0"*(6-len(str(lll[i]))) + str(lll[i]) )