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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

def solve(N,M):

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

    P = [0]*M

    Y = [0]*M

    for i in range(M):

        P[i],Y[i] = map(int, input().split())

        pref[P[i]-1].append(Y[i])

    for i in range(N):

        pref[i].sort()

    ans = []

    for i in range(M):

        ind = bisect_left(pref[P[i]-1],Y[i])

        ans.append('0'*(6-len(str(P[i])))+str(P[i])+'0'*(6-len(str(ind+1)))+str(ind+1))

    return ans

print(*solve(N,M),sep='\n')

def solve():

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

  A = [list(map(int, input().split()))+[i] for i in range(M)]



  A.sort(key=lambda x:(x[0],x[1]))

  ans = [0]*M

  before = -1

  for p,y,i in A:

    if p!=before:

      year = 1

    else:

      year += 1

    ans[i] = '0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(year)))+str(year)

    before = p

  return ans

print(*solve(),sep='\n')

N, M = map(int, input().split())
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort


def solve(N, M):
    pref = [[] for _ in range(N)]
    P = [0] * M
    Y = [0] * M
    for i in range(M):
        P[i], Y[i] = map(int, input().split())
        pref[P[i] - 1].append(Y[i])
    for i in range(N):
        pref[i].sort()
    ans = []
    for i in range(M):
        ind = bisect_left(pref[P[i] - 1], Y[i])
        ans.append(
            "0" * (6 - len(str(P[i])))
            + str(P[i])
            + "0" * (6 - len(str(ind + 1)))
            + str(ind + 1)
        )
    return ans


print(*solve(N, M), sep="\n")

def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) + [i] for i in range(M)]
    A.sort(key=lambda x: (x[0], x[1]))
    ans = [0] * M
    before = -1
    for p, y, i in A:
        if p != before:
            year = 1
        else:
            year += 1
        ans[i] = (
            "0" * (6 - len(str(p))) + str(p) + "0" * (6 - len(str(year))) + str(year)
        )
        before = p
    return ans


print(*solve(), sep="\n")

-N, M = map(int, input().split()) -from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort - - -def solve(N, M): -    pref = [[] for _ in range(N)] -    P = [0] * M -    Y = [0] * M -    for i in range(M): -        P[i], Y[i] = map(int, input().split()) -        pref[P[i] - 1].append(Y[i]) -    for i in range(N): -        pref[i].sort() -    ans = [] -    for i in range(M): -        ind = bisect_left(pref[P[i] - 1], Y[i]) -        ans.append( -            "0" * (6 - len(str(P[i]))) -            + str(P[i]) -            + "0" * (6 - len(str(ind + 1))) -            + str(ind + 1) +def solve(): +    N, M = map(int, input().split()) +    A = [list(map(int, input().split())) + [i] for i in range(M)] +    A.sort(key=lambda x: (x[0], x[1])) +    ans = [0] * M +    before = -1 +    for p, y, i in A: +        if p != before: +            year = 1 +        else: +            year += 1 +        ans[i] = ( +            "0" * (6 - len(str(p))) + str(p) + "0" * (6 - len(str(year))) + str(year) +        before = p -print(*solve(N, M), sep="\n") +print(*solve(), sep="\n")