# coding: utf-8

# Your code here!

from bisect import bisect_left





n,m = [int(i) for i in input().split()]

py = [[int(i) for i in input().split()] for _ in range(m)]



spy = list(sorted(py))



for p,y in py:

    l2 = bisect_left(spy,[p,y])

    l1 = bisect_left(spy,[p,0])

    print((format(p, '06')+format(l2-l1+1, '06')))
# coding: utf-8

# Your code here!



n,m = [int(i) for i in input().split()]

py = [[int(i) for i in input().split()] for _ in range(m)]



spy = list(sorted(py+[[p,0] for p in range(n+1)]))



zaatu = {(p,y):i for i, (p,y) in enumerate(spy)}





for p,y in py:

    print((format(p, '06')+format(zaatu[(p,y)]-zaatu[(p,0)], '06')))

# coding: utf-8
# Your code here!
from bisect import bisect_left

n, m = [int(i) for i in input().split()]
py = [[int(i) for i in input().split()] for _ in range(m)]
spy = list(sorted(py))
for p, y in py:
    l2 = bisect_left(spy, [p, y])
    l1 = bisect_left(spy, [p, 0])
    print((format(p, "06") + format(l2 - l1 + 1, "06")))

# coding: utf-8
# Your code here!
n, m = [int(i) for i in input().split()]
py = [[int(i) for i in input().split()] for _ in range(m)]
spy = list(sorted(py + [[p, 0] for p in range(n + 1)]))
zaatu = {(p, y): i for i, (p, y) in enumerate(spy)}
for p, y in py:
    print((format(p, "06") + format(zaatu[(p, y)] - zaatu[(p, 0)], "06")))

-from bisect import bisect_left - -spy = list(sorted(py)) +spy = list(sorted(py + [[p, 0] for p in range(n + 1)])) +zaatu = {(p, y): i for i, (p, y) in enumerate(spy)} -    l2 = bisect_left(spy, [p, y]) -    l1 = bisect_left(spy, [p, 0]) -    print((format(p, "06") + format(l2 - l1 + 1, "06"))) +    print((format(p, "06") + format(zaatu[(p, y)] - zaatu[(p, 0)], "06")))