from sys import stdin

import bisect



n,m = [int(x) for x in stdin.readline().rstrip().split()]

li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]



lin = [[]for _ in range(n)]

lin2 = []



for i in range(m):

    lin[li[i][0]-1].append(li[i][1])



for j in range(n):

    liv = sorted(lin[j])

    lin2.append(liv)



for k in range(m):

    tosi = str(li[k][0]).zfill(6)

    ban =  str(bisect.bisect(lin2[li[k][0]-1],li[k][1])).zfill(6)

    print((tosi+ban))
import bisect



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



li = [[] for _ in range(n+1)]

num = []



for _ in range(m):

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

    li[p].append(y)

    num.append((p,y))



for i in range(n+1):

    li[i].sort()



for i,j in num:

    print((str(i).zfill(6)+str(bisect.bisect_left(li[i],j)+1).zfill(6)))
from sys import stdin
import bisect

n, m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int, stdin.readline().rstrip().split())) for _ in range(m)]
lin = [[] for _ in range(n)]
lin2 = []
for i in range(m):
    lin[li[i][0] - 1].append(li[i][1])
for j in range(n):
    liv = sorted(lin[j])
    lin2.append(liv)
for k in range(m):
    tosi = str(li[k][0]).zfill(6)
    ban = str(bisect.bisect(lin2[li[k][0] - 1], li[k][1])).zfill(6)
    print((tosi + ban))

import bisect

n, m = list(map(int, input().split()))
li = [[] for _ in range(n + 1)]
num = []
for _ in range(m):
    p, y = list(map(int, input().split()))
    li[p].append(y)
    num.append((p, y))
for i in range(n + 1):
    li[i].sort()
for i, j in num:
    print((str(i).zfill(6) + str(bisect.bisect_left(li[i], j) + 1).zfill(6)))

-from sys import stdin -n, m = [int(x) for x in stdin.readline().rstrip().split()] -li = [list(map(int, stdin.readline().rstrip().split())) for _ in range(m)] -lin = [[] for _ in range(n)] -lin2 = [] -for i in range(m): -    lin[li[i][0] - 1].append(li[i][1]) -for j in range(n): -    liv = sorted(lin[j]) -    lin2.append(liv) -for k in range(m): -    tosi = str(li[k][0]).zfill(6) -    ban = str(bisect.bisect(lin2[li[k][0] - 1], li[k][1])).zfill(6) -    print((tosi + ban)) +n, m = list(map(int, input().split())) +li = [[] for _ in range(n + 1)] +num = [] +for _ in range(m): +    p, y = list(map(int, input().split())) +    li[p].append(y) +    num.append((p, y)) +for i in range(n + 1): +    li[i].sort() +for i, j in num: +    print((str(i).zfill(6) + str(bisect.bisect_left(li[i], j) + 1).zfill(6)))