import bisect

import collections



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

PM = [[int(j) for j in input().split()] for i in range(M)]

A = collections.defaultdict(list)

for x, y in sorted(PM):

    A[x] += [y]

for x, y in PM:

    z = bisect.bisect(A[x], y)

    print(('%06d%06d'%(x,z)))
# coding: utf-8

import sys



sr = lambda: sys.stdin.readline().rstrip()

ir = lambda: int(sr())

lr = lambda: list(map(int, sr().split()))



N, M = lr()

cur = [1] * (N+1)  # 1-indexed

PY = [lr() + [i] for i in range(M)]

PY.sort(key=lambda x: x[1])

answer = [None] * M  # 0-indexed

for p, y, i in PY:

    x = str(p).zfill(6) + str(cur[p]).zfill(6)

    answer[i] = x

    cur[p] += 1



for a in answer:

    print(a)

import bisect
import collections

N, M = list(map(int, input().split()))
PM = [[int(j) for j in input().split()] for i in range(M)]
A = collections.defaultdict(list)
for x, y in sorted(PM):
    A[x] += [y]
for x, y in PM:
    z = bisect.bisect(A[x], y)
    print(("%06d%06d" % (x, z)))

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
N, M = lr()
cur = [1] * (N + 1)  # 1-indexed
PY = [lr() + [i] for i in range(M)]
PY.sort(key=lambda x: x[1])
answer = [None] * M  # 0-indexed
for p, y, i in PY:
    x = str(p).zfill(6) + str(cur[p]).zfill(6)
    answer[i] = x
    cur[p] += 1
for a in answer:
    print(a)

-import bisect -import collections +# coding: utf-8 +import sys -N, M = list(map(int, input().split())) -PM = [[int(j) for j in input().split()] for i in range(M)] -A = collections.defaultdict(list) -for x, y in sorted(PM): -    A[x] += [y] -for x, y in PM: -    z = bisect.bisect(A[x], y) -    print(("%06d%06d" % (x, z))) +sr = lambda: sys.stdin.readline().rstrip() +ir = lambda: int(sr()) +lr = lambda: list(map(int, sr().split())) +N, M = lr() +cur = [1] * (N + 1)  # 1-indexed +PY = [lr() + [i] for i in range(M)] +PY.sort(key=lambda x: x[1]) +answer = [None] * M  # 0-indexed +for p, y, i in PY: +    x = str(p).zfill(6) + str(cur[p]).zfill(6) +    answer[i] = x +    cur[p] += 1 +for a in answer: +    print(a)