import sys

import collections

import itertools

import math

import re

from collections import Counter

from collections import deque

import bisect





MOD = 10 ** 9 + 7



N, M = [int(x) for x in input().split()]



KenList = [[] for _ in range(N)]



PYlist = [None] * M

for i in range(M):

    P, Y = [int(x) for x in input().split()]

    P = P - 1

    PYlist[i] = (P, Y)

    KenList[P].append((i, Y))





for i in range(N):

    KenList[i] = sorted(KenList[i], key=lambda x: x[1])



cityOrder = [None] * N

for i in range(N):

    kl = KenList[i]

    dic = {}

    for j in range(len(kl)):

        city = kl[j][0]

        dic[city] = j

    cityOrder[i] = dic





for i in range(M):

    ken = PYlist[i][0]

    kl = KenList[ken]

    idx = cityOrder[ken][i]

    # for j in range(len(kl)):

    #     if kl[j][0] == i:

    #         idx = j

    #         break



    print(("{0:06d}{1:06d}".format(ken+1, idx+1)))





sys.exit(0)

import sys

import collections

import itertools

import math

import re

from collections import Counter

from collections import deque



MOD = 10 ** 9 + 7



N, M = [int(x) for x in input().split()]



PYC = []

for i in range(M):

    p, y = [int(x) for x in input().split()]

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



PYC = sorted(PYC)



city = {}



pCount = 1

preP = -1

for p, y, c in PYC:

    if preP != p:

        pCount = 1

    city[c] = (p, pCount)

    pCount += 1

    preP = p



for i in range(M):

    print(("{:06d}{:06d}".format(city[i][0], city[i][1])))





sys.exit(0)

import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
import bisect

MOD = 10**9 + 7
N, M = [int(x) for x in input().split()]
KenList = [[] for _ in range(N)]
PYlist = [None] * M
for i in range(M):
    P, Y = [int(x) for x in input().split()]
    P = P - 1
    PYlist[i] = (P, Y)
    KenList[P].append((i, Y))
for i in range(N):
    KenList[i] = sorted(KenList[i], key=lambda x: x[1])
cityOrder = [None] * N
for i in range(N):
    kl = KenList[i]
    dic = {}
    for j in range(len(kl)):
        city = kl[j][0]
        dic[city] = j
    cityOrder[i] = dic
for i in range(M):
    ken = PYlist[i][0]
    kl = KenList[ken]
    idx = cityOrder[ken][i]
    # for j in range(len(kl)):
    #     if kl[j][0] == i:
    #         idx = j
    #         break
    print(("{0:06d}{1:06d}".format(ken + 1, idx + 1)))
sys.exit(0)

import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque

MOD = 10**9 + 7
N, M = [int(x) for x in input().split()]
PYC = []
for i in range(M):
    p, y = [int(x) for x in input().split()]
    PYC.append((p, y, i))
PYC = sorted(PYC)
city = {}
pCount = 1
preP = -1
for p, y, c in PYC:
    if preP != p:
        pCount = 1
    city[c] = (p, pCount)
    pCount += 1
    preP = p
for i in range(M):
    print(("{:06d}{:06d}".format(city[i][0], city[i][1])))
sys.exit(0)

-import bisect -KenList = [[] for _ in range(N)] -PYlist = [None] * M +PYC = [] -    P, Y = [int(x) for x in input().split()] -    P = P - 1 -    PYlist[i] = (P, Y) -    KenList[P].append((i, Y)) -for i in range(N): -    KenList[i] = sorted(KenList[i], key=lambda x: x[1]) -cityOrder = [None] * N -for i in range(N): -    kl = KenList[i] -    dic = {} -    for j in range(len(kl)): -        city = kl[j][0] -        dic[city] = j -    cityOrder[i] = dic +    p, y = [int(x) for x in input().split()] +    PYC.append((p, y, i)) +PYC = sorted(PYC) +city = {} +pCount = 1 +preP = -1 +for p, y, c in PYC: +    if preP != p: +        pCount = 1 +    city[c] = (p, pCount) +    pCount += 1 +    preP = p -    ken = PYlist[i][0] -    kl = KenList[ken] -    idx = cityOrder[ken][i] -    # for j in range(len(kl)): -    #     if kl[j][0] == i: -    #         idx = j -    #         break -    print(("{0:06d}{1:06d}".format(ken + 1, idx + 1))) +    print(("{:06d}{:06d}".format(city[i][0], city[i][1])))