from collections import defaultdict, deque, Counter

from heapq import heappush, heappop, heapify

from itertools import permutations, accumulate, combinations, combinations_with_replacement

from math import sqrt, ceil, floor, factorial

from bisect import bisect_left, bisect_right, insort_left, insort_right

from copy import deepcopy

from operator import itemgetter

from functools import reduce

from fractions import gcd

import sys

def input(): return sys.stdin.readline().rstrip()

def I(): return int(eval(input()))

def Is(): return list(map(int, input().split()))

def LI(): return list(map(int, input().split()))

def TI(): return tuple(map(int, input().split()))

def IR(n): return [I() for _ in range(n)]

def LIR(n): return [LI() for _ in range(n)]

def TIR(n): return [TI() for _ in range(n)]

def S(): return eval(input())

def Ss(): return input().split()

def LS(): return list(eval(input()))

def SR(n): return [S() for _ in range(n)]

def SsR(n): return [Ss() for _ in range(n)]

def LSR(n): return [LS() for _ in range(n)]

sys.setrecursionlimit(10**6)

MOD = 10**9+7

INF = 10**18

# ----------------------------------------------------------- #



n, m = Is()

PY = []

for i in range(m):

    p, y = Is()

    PY.append((i, p, y))

PY.sort(key=itemgetter(1, 2))

ANS = [[0]*2 for _ in range(m)]

tmp = -1

count = -1

for i, p, y in PY:

    if tmp != p:

        count = 1

        tmp = p

    else:

        count += 1

    ANS[i][0] = p

    ANS[i][1] = count

for a, b, in ANS:

    print(("{}{}".format(str(a).zfill(6), str(b).zfill(6))))

from collections import defaultdict, deque, Counter

from heapq import heappush, heappop, heapify

from itertools import permutations, accumulate, combinations, combinations_with_replacement

from math import sqrt, ceil, floor, factorial

from bisect import bisect_left, bisect_right, insort_left, insort_right

from copy import deepcopy

from operator import itemgetter

from functools import reduce, lru_cache  # @lru_cache(None)

from fractions import gcd

import sys

def input(): return sys.stdin.readline().rstrip()

def I(): return int(eval(input()))

def Is(): return (int(x) for x in input().split())

def LI(): return list(Is())

def TI(): return tuple(Is())

def IR(n): return [I() for _ in range(n)]

def LIR(n): return [LI() for _ in range(n)]

def TIR(n): return [TI() for _ in range(n)]

def S(): return eval(input())

def Ss(): return input().split()

def LS(): return list(S())

def SR(n): return [S() for _ in range(n)]

def SsR(n): return [Ss() for _ in range(n)]

def LSR(n): return [LS() for _ in range(n)]

sys.setrecursionlimit(10**6)

MOD = 10**9+7

INF = 10**18

# ----------------------------------------------------------- #



def compress(A):

    return {element: i+1 for i, element in enumerate(sorted(set(A)))}



n, m = Is()

PY = TIR(m)

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

for p, y in PY:

    A[p].append(y)

B = [compress(a) for a in A]



for p, y in PY:

    ans = str(p).zfill(6) + str(B[p][y]).zfill(6)

    print(ans)

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import (
    permutations,
    accumulate,
    combinations,
    combinations_with_replacement,
)
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys


def input():
    return sys.stdin.readline().rstrip()


def I():
    return int(eval(input()))


def Is():
    return list(map(int, input().split()))


def LI():
    return list(map(int, input().split()))


def TI():
    return tuple(map(int, input().split()))


def IR(n):
    return [I() for _ in range(n)]


def LIR(n):
    return [LI() for _ in range(n)]


def TIR(n):
    return [TI() for _ in range(n)]


def S():
    return eval(input())


def Ss():
    return input().split()


def LS():
    return list(eval(input()))


def SR(n):
    return [S() for _ in range(n)]


def SsR(n):
    return [Ss() for _ in range(n)]


def LSR(n):
    return [LS() for _ in range(n)]


sys.setrecursionlimit(10**6)
MOD = 10**9 + 7
INF = 10**18
# ----------------------------------------------------------- #
n, m = Is()
PY = []
for i in range(m):
    p, y = Is()
    PY.append((i, p, y))
PY.sort(key=itemgetter(1, 2))
ANS = [[0] * 2 for _ in range(m)]
tmp = -1
count = -1
for i, p, y in PY:
    if tmp != p:
        count = 1
        tmp = p
    else:
        count += 1
    ANS[i][0] = p
    ANS[i][1] = count
for (
    a,
    b,
) in ANS:
    print(("{}{}".format(str(a).zfill(6), str(b).zfill(6))))

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import (
    permutations,
    accumulate,
    combinations,
    combinations_with_replacement,
)
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys


def input():
    return sys.stdin.readline().rstrip()


def I():
    return int(eval(input()))


def Is():
    return (int(x) for x in input().split())


def LI():
    return list(Is())


def TI():
    return tuple(Is())


def IR(n):
    return [I() for _ in range(n)]


def LIR(n):
    return [LI() for _ in range(n)]


def TIR(n):
    return [TI() for _ in range(n)]


def S():
    return eval(input())


def Ss():
    return input().split()


def LS():
    return list(S())


def SR(n):
    return [S() for _ in range(n)]


def SsR(n):
    return [Ss() for _ in range(n)]


def LSR(n):
    return [LS() for _ in range(n)]


sys.setrecursionlimit(10**6)
MOD = 10**9 + 7
INF = 10**18
# ----------------------------------------------------------- #
def compress(A):
    return {element: i + 1 for i, element in enumerate(sorted(set(A)))}


n, m = Is()
PY = TIR(m)
A = [list() for _ in range(n + 1)]
for p, y in PY:
    A[p].append(y)
B = [compress(a) for a in A]
for p, y in PY:
    ans = str(p).zfill(6) + str(B[p][y]).zfill(6)
    print(ans)

-from functools import reduce +from functools import reduce, lru_cache  # @lru_cache(None) -    return list(map(int, input().split())) +    return (int(x) for x in input().split()) -    return list(map(int, input().split())) +    return list(Is()) -    return tuple(map(int, input().split())) +    return tuple(Is()) -    return list(eval(input())) +    return list(S()) +def compress(A): +    return {element: i + 1 for i, element in enumerate(sorted(set(A)))} + + -PY = [] -for i in range(m): -    p, y = Is() -    PY.append((i, p, y)) -PY.sort(key=itemgetter(1, 2)) -ANS = [[0] * 2 for _ in range(m)] -tmp = -1 -count = -1 -for i, p, y in PY: -    if tmp != p: -        count = 1 -        tmp = p -    else: -        count += 1 -    ANS[i][0] = p -    ANS[i][1] = count -for ( -    a, -    b, -) in ANS: -    print(("{}{}".format(str(a).zfill(6), str(b).zfill(6)))) +PY = TIR(m) +A = [list() for _ in range(n + 1)] +for p, y in PY: +    A[p].append(y) +B = [compress(a) for a in A] +for p, y in PY: +    ans = str(p).zfill(6) + str(B[p][y]).zfill(6) +    print(ans)