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

P=[]



for i in range(M):

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

	P.append( [i,x,y] )







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





prev_y=None

for idx,t in enumerate(P):

	x=t[0]; y=t[1]; z=t[2]



	if prev_y is None:

		cnt=1

	elif y!=prev_y:

		cnt=1

	else:

		cnt+=1



	P[idx].append(  "0"* (6-len(str(y)))+str(y)+"0"* (6-len(str(cnt)))+str(cnt) ) 



	prev_y=y



	



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





for x,y,z,w  in P:

	print(w)

# -*- coding: utf-8 -*-

import sys

from bisect import bisect_left, bisect_right



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

P=[ [] for _ in range(N+1) ]  #Prefecture 県

Q=[]    #クエリー



for _ in range(M):

    p,y=list(map(int, sys.stdin.readline().split()))

    P[p].append(y)

    Q.append((p,y))



for i in range(1,N+1):

    P[i].sort()



for i,y in Q:

    print(str(i).zfill(6)+str(bisect_left(P[i],y)+1).zfill(6))
N, M = list(map(int, input().split()))
P = []
for i in range(M):
    x, y = list(map(int, input().split()))
    P.append([i, x, y])
P.sort(key=lambda x: (x[1], x[2]))
prev_y = None
for idx, t in enumerate(P):
    x = t[0]
    y = t[1]
    z = t[2]
    if prev_y is None:
        cnt = 1
    elif y != prev_y:
        cnt = 1
    else:
        cnt += 1
    P[idx].append(
        "0" * (6 - len(str(y))) + str(y) + "0" * (6 - len(str(cnt))) + str(cnt)
    )
    prev_y = y
P.sort(key=lambda x: x[0])
for x, y, z, w in P:
    print(w)

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N, M = list(map(int, sys.stdin.readline().split()))
P = [[] for _ in range(N + 1)]  # Prefecture 県
Q = []  # クエリー
for _ in range(M):
    p, y = list(map(int, sys.stdin.readline().split()))
    P[p].append(y)
    Q.append((p, y))
for i in range(1, N + 1):
    P[i].sort()
for i, y in Q:
    print(str(i).zfill(6) + str(bisect_left(P[i], y) + 1).zfill(6))

-N, M = list(map(int, input().split())) -P = [] -for i in range(M): -    x, y = list(map(int, input().split())) -    P.append([i, x, y]) -P.sort(key=lambda x: (x[1], x[2])) -prev_y = None -for idx, t in enumerate(P): -    x = t[0] -    y = t[1] -    z = t[2] -    if prev_y is None: -        cnt = 1 -    elif y != prev_y: -        cnt = 1 -    else: -        cnt += 1 -    P[idx].append( -        "0" * (6 - len(str(y))) + str(y) + "0" * (6 - len(str(cnt))) + str(cnt) -    ) -    prev_y = y -P.sort(key=lambda x: x[0]) -for x, y, z, w in P: -    print(w) +# -*- coding: utf-8 -*- +import sys +from bisect import bisect_left, bisect_right + +N, M = list(map(int, sys.stdin.readline().split())) +P = [[] for _ in range(N + 1)]  # Prefecture 県 +Q = []  # クエリー +for _ in range(M): +    p, y = list(map(int, sys.stdin.readline().split())) +    P[p].append(y) +    Q.append((p, y)) +for i in range(1, N + 1): +    P[i].sort() +for i, y in Q: +    print(str(i).zfill(6) + str(bisect_left(P[i], y) + 1).zfill(6))