import sys

input = sys.stdin.readline

f = lambda:list(map(int,input().split()))

n,m = f()

llm = []

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

ll = []

for i in range(m):

  p,y = f()

  llm.append([i,p,y])

  lln[p-1].append([y,i])

for j in range(n):

  lln[j].sort()

  for k in range(len(lln[j])):

    ll.append([lln[j][k][1],j+1,k+1])

ll.sort()

for i in range(m):

  print((str(ll[i][1]).zfill(6)+str(ll[i][2]).zfill(6)))
import sys

input = sys.stdin.readline

f = lambda:list(map(int,input().split()))

n,m = f()

ll = [list(f()) for _ in range(m)]

l = [0]*n

d = {}

for p,y in sorted(ll,key=lambda k:k[1]):

  l[p-1] += 1

  d[y] = str(p).zfill(6)+str(l[p-1]).zfill(6)

for l in ll:

  print((d[l[1]]))
import sys

input = sys.stdin.readline
f = lambda: list(map(int, input().split()))
n, m = f()
llm = []
lln = [[] for _ in range(n)]
ll = []
for i in range(m):
    p, y = f()
    llm.append([i, p, y])
    lln[p - 1].append([y, i])
for j in range(n):
    lln[j].sort()
    for k in range(len(lln[j])):
        ll.append([lln[j][k][1], j + 1, k + 1])
ll.sort()
for i in range(m):
    print((str(ll[i][1]).zfill(6) + str(ll[i][2]).zfill(6)))

import sys

input = sys.stdin.readline
f = lambda: list(map(int, input().split()))
n, m = f()
ll = [list(f()) for _ in range(m)]
l = [0] * n
d = {}
for p, y in sorted(ll, key=lambda k: k[1]):
    l[p - 1] += 1
    d[y] = str(p).zfill(6) + str(l[p - 1]).zfill(6)
for l in ll:
    print((d[l[1]]))

-llm = [] -lln = [[] for _ in range(n)] -ll = [] -for i in range(m): -    p, y = f() -    llm.append([i, p, y]) -    lln[p - 1].append([y, i]) -for j in range(n): -    lln[j].sort() -    for k in range(len(lln[j])): -        ll.append([lln[j][k][1], j + 1, k + 1]) -ll.sort() -for i in range(m): -    print((str(ll[i][1]).zfill(6) + str(ll[i][2]).zfill(6))) +ll = [list(f()) for _ in range(m)] +l = [0] * n +d = {} +for p, y in sorted(ll, key=lambda k: k[1]): +    l[p - 1] += 1 +    d[y] = str(p).zfill(6) + str(l[p - 1]).zfill(6) +for l in ll: +    print((d[l[1]]))