In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.
City i is established in year Y_i and belongs to Prefecture P_i.
You can assume that there are no multiple cities that are established in the same year.
It is decided to allocate a 12-digit ID number to each city.
If City i is the x-th established city among the cities that belong to Prefecture i, the first six digits of the ID number of City i is P_i, and the last six digits of the ID number is x.
Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.
Find the ID numbers for all the cities.
Note that there can be a prefecture with no cities.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 1 \leq M \leq 10^5
 - 1 \leq P_i \leq N
 - 1 \leq Y_i \leq 10^9
 - Y_i are all different.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
P_1 Y_1
:
P_M Y_M

-----Output-----
Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, ...).

-----Sample Input-----
2 3
1 32
2 63
1 12

-----Sample Output-----
000001000002
000002000001
000001000001

 - As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.
 - As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.
 - As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.

Difficulty: introductory

Starter code:

Solutions:
import bisect

n,m = map(int,input().split())

Q = []
P = [[] for _ in range(n)]
for i in range(m):
    p,y = map(int,input().split())
    Q.append([p,y])
    P[p-1].append(y)

P_1 = [sorted(l) for l in P]

for p,y in Q:
    a = str(p).zfill(6)
    b = str(bisect.bisect(P_1[p-1], y)).zfill(6)
    print(a+b)

from bisect import bisect_left
n,m = map(int, input().split())
py = []
l = [[] for _ in range(n+1)]
for _ in range(m):
  p,y = map(int, input().split())
  l[p].append(y)
  py.append((p,y))
  
for i in l: i.sort()

for p,y in py:
  s = str(p)
  t = str(bisect_left(l[p],y)+1)
  ans = "0"*(6-len(s))+s + "0"*(6-len(t))+t
  print(ans)

n, m = list(map(int, input().split()))
p_y = []
for i in range(m):
    p, y = list(map(int, input().split()))
    p_y.append([p, y, i])

p_y.sort()
# print(p_y)

res = [0] * m
order = 0
for i in range(m):
    ken, _, index = p_y[i]
    if ken != p_y[i - 1][0] and i > 0:
        order = 1
    else:
        order += 1
    res[index] = [ken, order]


# print(res)

for i in range(m):
    ken = str(res[i][0]).zfill(6)
    order = str(res[i][1]).zfill(6)
    print((ken + order))


from collections import defaultdict


N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) for _ in range(M)]

di = defaultdict(list)

for i, py in enumerate(PY):
    di[py[0]].append([py[1], i])

ans = ["" for _ in range(M)]

for k, v in list(di.items()):
    v.sort()

    for j, yi in enumerate(v):
        s = str(k).zfill(6)
        t = str(j + 1).zfill(6)
        ans[yi[1]] = s + t

print(("\n".join(ans)))


n,m=map(int,input().split())


citylis=[[] for i in range(n)]
for i in range(1,m+1):
  pi,yi=map(int,input().split())
  citylis[pi-1].append([i,yi])

for i in range(n):
  if len(citylis[i])!=0:
    citylis[i].sort(key=lambda x:x[1])

lis=[]
for i in range(n):
  for j in range(len(citylis[i])):
    cityposi=str(i+1)
    cityposi="0"*(6-len(cityposi))+cityposi
    ordernum=str(j+1)
    ordernum="0"*(6-len(ordernum))+ordernum
    lis.append([citylis[i][j][0],cityposi+ordernum])

lis.sort(key=lambda x:x[0])
for i in range(m):
  print(lis[i][1])

from collections import defaultdict
import bisect
N,M = map(int, input().split())
dic = defaultdict(list)
cities = []
for _ in range(M):
  p,y = map(int,input().split())
  cities.append([p,y])
for item in sorted(cities):
  dic[item[0]].append(item[1])
for item in cities:
  print("%06d%06d"%(item[0],bisect.bisect(dic[item[0]],item[1])))

from collections import defaultdict

n, m = list(map(int, input().split()))
prefecture = [[] for _ in range(n+1)]
tpl_lst=[]
for i in range(m):
    p, y = list(map(int, input().split()))
    prefecture[p].append(y)
    tpl_lst.append((p,y))

for p in prefecture:
    if len(p)>=2:
        p.sort()

d = defaultdict(list)
for idx, pre in enumerate(prefecture):
    if len(pre)>=1:
        for i, year in enumerate(pre):
            d[(idx, year)]=[idx, i+1]

for tpl in tpl_lst:
    id = d[tpl][0]*(10**6) + d[tpl][1]
    id = str(id)
    id = "0"*(12-len(id)) + id
    print(id)
#print(prefecture)


import math

n, m = map(int, input().split(" "))
pyL = sorted([[i] + list(map(int,
                             input().split(" "))) for i in range(m)],
             key=lambda x: x[2])

li = [1] * (n + 1)

for i in range(len(pyL)):
    index, p, y = pyL[i]
    pyL[i].append(str(p).zfill(6) + str(li[p]).zfill(6))
    li[p] += 1

for py in sorted(pyL, key=lambda x: x[0]):
    print(py[3])

N, M = list(map(int, input().split()))
li = [0] * M

for i in range(M):
    P, Y = list(map(int, input().split()))
    li[i] = (P, Y)

li2 = sorted(li)

s = '000000'
tmp = 0
cnt = 1
dic = {}
for i in li2:
    if tmp == i[0]:
        cnt += 1
    else:
        cnt = 1
        tmp = i[0]

    s1 = s[0:6-len(str(i[0]))] + str(i[0])
    s2 = s[0:6-len(str(cnt))] + str(cnt)
    s3 = s1 + s2
    dic[i] = s3

for i in li:
    print((dic[i]))


from collections import deque
n,m = list(map(int,input().split()))
prefs = [{} for _ in range(n)]
cities = deque()
for i in range(m):
    p, y = list(map(int,input().split()))
    prefs[p-1][y] = -1
    cities.append((p,y))

for p in prefs:
    years = list(p.keys())
    years.sort()
    for y in range(len(years)):
        p[years[y]] = y+1


for _ in range(m):
    p, y = cities.popleft()
    cid = prefs[p-1][y] + p * 1000000
    print(("{:0=12}".format(cid)))


n, m = map(int, input().split())
py = [list(map(int, input().split())) for i in range(m)]

ipy = [[0, 0, 0]]
for i in range(m):
    ipy.append([i] + py[i])
ipy = sorted(ipy, key=lambda x: (x[1], x[2]))
for i in range(1, m+1):
    if ipy[i][1] != ipy[i-1][1]:
        cnt = 0
    cnt += 1
    ipy[i].append(str(ipy[i][1]).zfill(6) + str(cnt).zfill(6))
ipy = sorted(ipy)
for i in range(1, m+1):
    print(ipy[i][3])

n,m = map(int,input().split())
py = [[i+1]+list(map(int,input().split())) for i in range(m)]
pysort = sorted(py,key=lambda x:(x[1],x[2]))

j = 1
cnt = 0
for i in range(m):
    while True:
        if pysort[i][1] == j:
            cnt += 1
            #pysort[i] += [f"{pysort[i][1]}:{cnt}"]
            pysort[i] += [str(pysort[i][1]).zfill(6)+str(cnt).zfill(6)]
            break
        else:
            cnt = 0
            j += 1

pysortsort = sorted(pysort,key=lambda x:x[0])
[print(a[3]) for a in pysortsort]

n, m = list(map(int, input().split()))
py = []

for i in range(m):
    _p, _y = list(map(int, input().split()))
    py.append([_p, _y, i])

py = sorted(py, key=lambda x: (x[0], x[1]))
ans = []
p = -1
x = 1

for i in range(m):
    if p != py[i][0]:
        x = 1
        p = py[i][0]
    else:
        x += 1

    pid = str(py[i][0]).zfill(6)
    xid = str(x).zfill(6)
    ans.append([pid+xid, py[i][2]])

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

for a, i in ans:
    print(a)



import bisect
n,m = map(int,input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
  s,t = map(int,input().split())
  p.append(s)
  y.append(t)
  x[s-1].append(t)
for i in range(n):
  x[i].sort()
  
for i in range(m):
  index = bisect.bisect_left(x[p[i]-1],y[i])
  print("{:06}{:06}".format(p[i],index+1))

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)
#index(x) が重い => indexを使わなくて良いようにする

N, M = map(int, input().split())
#d = [list() for _ in range(N)]
dic = dict()
dic2 = dict()
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    #d[p-1].append(y)
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))

#year sort O(N log N) => 重い　dict使用
#for i in range(N):
#    d[i].sort()
for key in dic.keys():
    dic[key].sort()

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1
#search O(M)***
for i in range(M):
    p, y = P[i]
    #ans = str(p).zfill(6)+str(d[p-1].index(y)+1).zfill(6)
    # zfill 重い？
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    #t = dic[p].index(y)+1
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    print(ans)

class City:
    def __init__(self, prefecture, year):
        self.prefecture = prefecture
        self.year = year
        self.order = None

    def __eq__(self, other):
        if self.year == other.year:
            return True
        return False

    def __le__(self, other):
        if self.year <= other.year:
            return True
        return False

    def __lt__(self, other):
        if self.year < other.year:
            return True
        return False

    def __ge__(self, other):
        if self.year >= other.year:
            return True
        return False

    def __gt__(self, other):
        if self.year > other.year:
            return True
        return False


cities = []
n,m=[int(i) for i in input().split()]
prefecture=[[] for i in range(n+1)]



for i in range(m):
    p,y=[int(j) for j in input().split()]
    new_city=City(p, y)
    cities.append(new_city)
    prefecture[p].append(new_city)

for pref_list in prefecture:
    pref_list.sort()
    for i ,pref in enumerate(pref_list):
        pref.order=i+1

for city in cities:
    print((str(city.prefecture).zfill(6)+str(city.order).zfill(6)))




n,m=list(map(int,input().split()))
pref=[[] for _ in range(n+1)]
py = [[i]+list(map(int,input().split())) for i in range(m)]
py.sort(key=lambda x: (x[1],x[2]))
ans=list()
now=0
cnt=0
for x in py:
  cnt = 1 if now != x[1] else cnt + 1
  now = x[1]
  ans.append([x[0],x[1],cnt])
ans.sort(key=lambda x:x[0])
for x in ans:
  print((str(x[1]).zfill(6)+str(x[2]).zfill(6)))




import sys
from collections import deque


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return list(map(int, stdin.readline().split()))
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, m = nm()
    Y = [deque() for _ in range(n)]
    Y_id = []
    order = []
    for i in range(m):
        p, y = nm()
        Y[p - 1].append(y)
        order.append(p)

    for y in Y:
        d = {}
        for i, y_s in enumerate(sorted(y)):
            d[y_s] = i + 1
        Y_id += [d]

    for o in order:
        print(('{:06}'.format(o) +
              '{:06}'.format(Y_id[o - 1][Y[o - 1].popleft()])))


def __starting_point():
    main()

__starting_point()

import collections
import bisect
n,m=map(int,input().split())
p=[[int(j) for j in input().split()] for i in range(m)]
a=collections.defaultdict(list)
for x,y in sorted(p):
    a[x]+=[y]
for x,y in p:
    z=bisect.bisect(a[x],y)
    print("%06d%06d"%(x,z))

from collections import defaultdict
(n, m), *q = [[*list(map(int, i.split()))] for i in open(0)]
d = defaultdict(list)
for k, v in q:
    d[k].append(v)
c = defaultdict(dict)
for k, v in list(d.items()):
    for i, j in enumerate(sorted(v)):
        c[k][j] = i + 1
for p, y in q:
    print(("{:0>6}{:0>6}".format(p, c[p][y])))


import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():

    N, M = NMI()
        
    PY = [[m,NLI()] for m in range(M)]
    
    PY = list(sorted(list(sorted(PY,key = lambda x : x[1][1])),key = lambda x : x[1][0]))
    

    
    city = PY[0][1][0]
    cnt = 0

    for m in range(M):
        if PY[m][1][0] == city:
            cnt += 1
        else:
            city = PY[m][1][0]
            cnt = 1
            
        PY[m][1] = str(PY[m][1][0]).zfill(6) + str(cnt).zfill(6)
    
    PY = list(sorted(PY))
    
    
    for m in range(M):
        print(PY[m][1])


def __starting_point():
    main()
__starting_point()

import sys
from collections import defaultdict

(n, m), *q = [[*list(map(int, i.split()))] for i in sys.stdin]
d = defaultdict(list)
for k, v in q:
    d[k].append(v)
c = defaultdict(dict)
for k, v in list(d.items()):
    for i, j in enumerate(sorted(v)):
        c[k][j] = i + 1
for p, y in q:
    print(("{:0>6}{:0>6}".format(p, c[p][y])))


N, M = [int(x) for x in input().split()]
C = [0 for _ in range(N)]
V = []
IDs = []
for i in range(M):
    P, Y = [int(x) for x in input().split()]
    V.append([Y, P, i])
V.sort()
for v in V:
    C[v[1] - 1] += 1
    x = C[v[1] - 1]
    IDs.append(f"{v[2]:06d}{v[1]:06d}{x:06d}")
IDs.sort()
for i in IDs:
    print((i[6:]))


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

PY.sort(key=lambda x:x[1])
ans = []
cnt = [0] * N
for p, y, i in PY:
  ans.append(("{0:06d}".format(p)+"{0:06d}".format(cnt[p-1]+1), i))
  cnt[p-1] += 1
ans.sort(key=lambda x:x[1])
for a in ans:
  print((a[0]))




n, m = list(map(int, input().split()))

order = [[] for i in range(n + 1)]
id_perf_map = [-1 for i in range(m + 1)]

for i in range(1, m + 1):
    p, y = list(map(int, input().split()))
    id_perf_map[i] = p
    order[p].append((i, y))

id_num_map = [-1 for i in range(m + 1)]

for i in range(1, n + 1):
    order[i] = list(sorted(order[i], key=lambda x: x[1]))
    for idx, (city_id, _) in enumerate(order[i]):
        id_num_map[city_id] = idx + 1

for i in range(1, m + 1):
    print(('{:06}{:06}'.format(id_perf_map[i], id_num_map[i])))



import bisect

n,m=list(map(int,input().split()))

ans=[]

re=[[] for _ in range(n)]



for _ in range(m):
  a=list(map(int,input().split()))
  re[a[0]-1].append(a[1])
  ans.append(a)
  
d=[]
for f in re:
  sor=[]
  
  new=sorted(list(set(f)))
  
  for i in f:
    c=bisect.bisect_left(new,i)
    sor.append(c+1)
    
  d.append(sor)
    
  
for x in ans:
  p=x[0]
  q=d[p-1].pop(0)
  print((str('{:0=6}'.format(p))+str('{:0=6}'.format(q))))
  




n,m = map(int, input().split())
pyl = [ [] for _ in range(n+1) ]

for i in range(m):
    p,y = map(int, input().split())
    pyl[p].append((y,i))

ans = ['']*m
for p, yil in enumerate(pyl):
    top = str(p).zfill(6)
    yil.sort()
    for order,(y,i) in enumerate(yil):
        bottom = order+1
        bottom = str(bottom).zfill(6)
        ans[i] = top+bottom

for a in ans:
    print(a)

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

p_dict = {}

for i in range(M):
  p, y = map(int, input().split())
  if p not in p_dict.keys():
    p_dict[p] = [[y, p, i]]
  else:
    p_dict[p].append([y, p, i])
  
ans = []
for p in p_dict.keys():
  p_dict[p].sort()
  for i in range(len(p_dict[p])):
    p_dict[p][i].append(i + 1)
    ans.append(p_dict[p][i])
    
ans.sort(key=lambda x: x[2])
for y, p, oi, si in ans:
  print("{:06d}{:06d}".format(p, si))

n, m = map(int,input().split())
numbers = [{} for _ in range(n)]

for i in range(m):
    p, y = map(int,input().split())
    numbers[p-1][i] = y #pで県を指定して、iで順番の情報を保つ

answers = {}

for i in range(n):
    number = numbers[i]
    if len(number) == 0:
        continue
    new_number = sorted(number.items(), key = lambda x : x[1]) #x[1]で誕生ねんでソート
    cnt = 1
    for num in new_number:
        answers[num[0]] = (6-len(str(i+1)))*'0' + str(i+1) + (6-len(str(cnt)))*'0' + str(cnt)
        cnt += 1

answer = sorted(answers.items(), key = lambda x : x[0])

for i in answer:
    print(i[1])

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

C = []
for i in range(M):
    p, y = list(map(int, input().split()))
    C.append([i, p, y])
C.sort(key=lambda x: (x[1], x[2]))

ans = []
k = C[0][1]
n = 1
for i in range(M):
    city = C[i][1]
    if k != city:
        k = city
        n = 1
    number = f'{city:06}{n:06}'
    ans.append([C[i][0], number])
    n += 1
ans.sort(key=lambda x: x[0])
for i in range(M):
    print((ans[i][1]))


from collections import defaultdict
N, M = list(map(int, input().split()))
L = []
A = []
for _ in range(M):
    p, y = list(map(int, input().split()))
    L.append([p, y])
    A.append([p, y])

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

ans_d = defaultdict()
dp = [0] * (N + 1)
for i, v in enumerate(L):
    # k = 6 - len(str(v[0]))
    s = ''
    if (dp[v[0]] != 0):
        l_dp = 6 - len(str(dp[v[0]] + 1))
        for j in range(l_dp):
            s += '0'

        s += str(dp[v[0]] + 1)
        dp[v[0]] += 1
    else:
        l_dp = 6 - len(str(dp[v[0]] + 1))
        for j in range(l_dp):
            s += '0'
        s += str(dp[v[0]] + 1)
        dp[v[0]] += 1
    k = str(v[0]) + ' ' + str(v[1])
    ans_d[k] = s

for i in A:
    m = str(i[0]) + ' ' + str(i[1])
    k = 6 - len(str(i[0]))
    s = ''
    for j in range(k):
        s += '0'
    s += str(i[0])
    print((s + ans_d[m]))


N,M = map(int,input().split())
P = [list(map(int,input().split())) for i in range(M)]
for i in range(M):
    P[i].append(i)
P.sort(key=lambda x: x[1])
B = [1]*N

for i in range(M):
    P[i] += "0"*(6 - len(str(P[i][0]))) + str(P[i][0]) + "0"*(6 - len(str(B[P[i][0]-1]))) + str(B[P[i][0]-1]),
    B[P[i][0]-1] += 1
    
P.sort(key=lambda x: x[2])
for i in range(M):
    print(P[i][3])

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, M = MI()
    L = []
    
    for i in range(M):
        temp = [i]+LI()
        L.append(temp)
    L.sort(key = lambda x: x[2])
    L.sort(key = lambda x: x[1])
    ans = [0]*M
    D = defaultdict(int)
    for a,b,c in L:
        D[b]+=1
        c = D[b]
        ans[a] = str(b).zfill(6)+str(c).zfill(6)
    
    for i in ans:
        print(i)

def __starting_point():
    main()
__starting_point()

from collections import defaultdict
 
 
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]
 
di = defaultdict(list)
 
for i, py in enumerate(PY):
    di[py[0]].append([py[1], i])
 
ans = ["" for _ in range(M)]
 
for k, v in di.items():
    v.sort()
 
    for j, yi in enumerate(v):
        s = str(k).zfill(6)
        t = str(j + 1).zfill(6)
        ans[yi[1]] = s + t
 
print("\n".join(ans))

n,m=map(int,input().split())
d=[0]*m
K=[[] for i in range(n)]
for i in range(m):
  p,y=map(int,input().split())
  K[p-1].append((i,y))
for i in range(n):
  K[i].sort(key=lambda x: x[1])
  c=1
  for a,b in K[i]:
    ken=str(i+1)
    t=str(c)
    d[a]=str('0'*(6-len(ken)))+ken+str('0'*(6-len(t)))+t
    c+=1
for i in d:
  print(i)

N, M = list(map(int, input().split()))
keep = [[] for i in range(N)]
keep2 = []


for i in range(M):
    p, y = list(map(int, input().split()))
    keep[p - 1].append([i, p, y])


for i in range(N):
    keep[i] = sorted(keep[i], key=lambda x: x[2])

for i in range(N):
    biggest = len(keep[i])
    j = 0
    while j < biggest:
        keep[i][j][2] = j + 1
        j += 1
    keep2 += keep[i]

keep2 = sorted(keep2, key=lambda x: x[0])

for i in range(M):
    ans = ''
    ans += '0' * (6 - len(str(keep2[i][1]))) + str(keep2[i][1])
    ans += '0' * (6 - len(str(keep2[i][2]))) + str(keep2[i][2])
    print(ans)


N, M = list(map(int, input().split()))
PY = []
for i in range(M):
    PY.append([i] + list(map(int, input().split())))

PY.sort(key=lambda x: x[2])
ans = []
C = [0] * (N+1)
for i, P, Y in PY:
    C[P] += 1
    ans.append([i, '{:0=6}{:0=6}'.format(P, C[P])])
ans.sort()
for i, a in ans:
    print(a)


N,M=map(int,input().split())
A=[]
for i in range(M):
    P,Y=map(int,input().split())
    A.append([P,Y,i])

ans=[""]*M
A=sorted(A, key=lambda x: x[1])
A=sorted(A,key=lambda x:x[0])

now=A[0][0]
cnt=1
for i in range(M):
    pref=str(A[i][0])
    
    if A[i][0]!=now:
        cnt=1
    year=str(cnt)
    now=A[i][0]
    cnt+=1

    ans[A[i][2]]=pref.zfill(6)+year.zfill(6)

for i in range(M):
    print(ans[i])

N,M = map(int,input().split())
py = [list(map(int,input().split()))+[i] for i in range(M)]
py.sort()
P = py[0][0]
c = 0
ans = []
for p,y,i in py:
    if p == P:
        c += 1
    else:
        P = p
        c = 1
    ansc = str(c)
    ansp = str(p)
    anser = "0" * (6-len(ansp)) + ansp + "0" *(6-len(ansc)) + ansc
    ans.append([i,anser])
ans.sort()
for i,anser in ans:
    print(anser)

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

sortPY = sorted(PY, key=lambda x: x[1])
prefec = [0]*(N+1)
res = []
for p, y, i in sortPY:
    prefec[p] += 1
    strp = str(p)
    ID = '0'*(6-len(strp)) + strp + '0'*(6-len(str(prefec[p]))) + str(prefec[p])
    res.append([ID, i])

sortres = sorted(res, key=lambda x: x[1])
for i in range(M):
    print((sortres[i][0]))


N,M=map(int,input().split())
PY=[list(map(int,input().split())) for i in range(M)]
PYI=sorted([(p,y,i) for i,(p,y) in enumerate(PY)])
r=['']*M
a,b=0,0
for p,y,i in PYI:
    if a!=p:
        a,b=p,1
    else:
        b+=1
    r[i]=str(p).zfill(6)+str(b).zfill(6)
print(*r,sep='\n')

def __starting_point():
	n,m = list(map(int,input().split()))

	A = []
	for i in range(m):
		a,b = list(map(int,input().split()))
		A.append([a,b,i,""])

	#各内部配列でソートする
	B = sorted(A,key=lambda x:(x[0],x[1]))

	no = 1
	tmp = 0
	for b in B:
		if tmp == b[0]:
			no += 1
		else:
			tmp = b[0]
			no = 1

		#市通番
		cityno = str(b[0]).zfill(6) + str(no).zfill(6)
		b[3] = cityno

	#再ソートする
	C = sorted(B,key=lambda x:(x[2]))
	
	for c in C:
		print((c[3]))

__starting_point()

N, M = list(map(int, input().split()))
P = [0] * M
for i in range(M):
    P[i] = list(map(int, input().split())) + [i + 1]

P = sorted(P, key = lambda x: x[1])
P = sorted(P, key = lambda x: x[0])

a = P[0][0]
c = 0
for i in range(M):
    #print(P[i])
    if P[i][0] == a:
        c += 1
        P[i].append(c)
    else:
        c = 1
        a = P[i][0]
        P[i].append(c)
    #print(P[i])

P = sorted(P, key = lambda x: x[2])
for i in range(M):
    s = str(P[i][0]).zfill(6)
    ss = str(P[i][3]).zfill(6)
    print((s + ss))




import bisect
n,m = map(int, input().split(" "))
py = [list(map(int, input().split(" "))) for i in range(m)]
n_py = sorted(py)
a = [[] for i in range(n+1)]
for i,j in py:
  a[i].append(j)
for i in range(1, n+1):
  a[i] = sorted(a[i])
#print(a)
#print(py)
for i, j in py:
  ix, ij = map(str, [i, bisect.bisect(a[i], j)])
  
  print("0"*(6-len(ix))+ ix + "0"*(6-len(ij))+ij)

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

for i in range(m):
    ab[i].append(i)

ab_l = sorted(ab, key=lambda x: x[1])
ab_ll = sorted(ab_l, key=lambda x: x[0])

temp = 1
for j in range(m):
    if j==0 or ab_ll[j][0] != ab_ll[j-1][0]:
        temp = 1
    else:
        temp +=1
    ab_ll[j].append(temp)

ab_lll = sorted(ab_ll, key=lambda x: x[2])

for i in range(m):
    print(str(ab_lll[i][0]).zfill(6)+str(ab_lll[i][3]).zfill(6))

n, m = map(int, input().split())

py = []
for i in range(m):
    p, y = map(int, input().split())
    py.append([i, p, y])
cnt = [0] * (n + 1)

sorted_py = sorted(py, key = lambda x: (x[1], x[2]))
for i in range(m):
    cnt[sorted_py[i][1]] += 1
    city_id = str(sorted_py[i][1]).zfill(6)+str(cnt[sorted_py[i][1]]).zfill(6)
    sorted_py[i].append(city_id)

sorted_py = sorted(sorted_py, key = lambda x: x[0])
for i in range(m):
    print(sorted_py[i][3])

n,m=list(map(int,input().split()))
pre=[[] for i in range(n)]
pre_num=[[] for i in range(n)]
city=[]

for i in range(m):
  #pの県に属してy年にできた
  p,y=list(map(int,input().split()))
  pre[p-1].append(y)
  city.append(p-1)

from bisect import bisect_right

for i in range(n):
  town=sorted(pre[i])
  for j in range(len(town)):
    pre_num[i].append(bisect_right(town,pre[i][j]))

cnt=[0 for i in range(n)]
for i in city:
  print((str(i+1).zfill(6)+str(pre_num[i][cnt[i]]).zfill(6)))
  cnt[i]+=1
  


  


# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)
#index(x) が重い => indexを使わなくて良いようにする

N, M = map(int, input().split())
#d = [list() for _ in range(N)]
dic = dict()
dic2 = dict()
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    #d[p-1].append(y)
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))

#year sort O(N log N) => 重い　dict使用
#for i in range(N):
#    d[i].sort()
for key in dic.keys():
    dic[key].sort()

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1
#search O(M)***
for i in range(M):
    p, y = P[i]
    ans = str(p).zfill(6)+str(dic2[y]).zfill(6)
    """
    # zfill 重い？
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    #t = dic[p].index(y)+1
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    """
    print(ans)

def make_code(prifacture_num, city_num):
    s1 = str(prifacture_num)
    while len(s1) != 6:
        s1 = '0' + s1
    s2 = str(city_num)
    while len(s2) != 6:
        s2 = '0' + s2
    return s1 + s2


prifacture_cnt, city_cnt = list(map(int, input().split()))
data = [list(map(int, input().split())) for i in range(city_cnt)]
city_data = []

for i in range(city_cnt):
    city_data.append([data[i][0], data[i][1], i])

city_data.sort()
city_code = []
prifacture = city_data[0][0]
cnt = 0
for city in city_data:
    if prifacture == city[0]:
        cnt+=1
        s = make_code(prifacture, cnt)
        city_code.append([city[2], s])
    else:
        cnt = 1
        prifacture = city[0]
        s = make_code(prifacture, cnt)
        city_code.append([city[2], s])

city_code.sort()
for num,code in city_code:
    print(code)


import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *PY = map(int, read().split())
    city = [(p, y, i) for i, (p, y) in enumerate(zip(*[iter(PY)] * 2))]

    city.sort(key=itemgetter(1))

    counter = [0] * (N + 1)
    ans = [0] * M
    for p, y, i in city:
        counter[p] += 1
        ans[i] = f"{p:>06}{counter[p]:>06}"

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

    return


def __starting_point():
    main()

__starting_point()

def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    PY = [[i]+list(map(int,input().split())) for i in range(M)]

    PY = sorted(PY,key = lambda x:(x[1],x[2]))
    
    ans_li = ['0'*12]*M
    town_dict = {}

    for idx,p,y in PY:
        x = town_dict.get(p,1)

        id_ = ('{:6d}'.format(p)+'{:6d}'.format(x)).replace(' ','0')
        ans_li[idx] = id_

        town_dict[p] = town_dict.get(p,1)+1

    print('\n'.join(ans_li))
    
def __starting_point():
    main()
__starting_point()

#!/usr/bin/env python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

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

iPY.sort(key=lambda x: (x[1], x[2]))

ans = []
cnt = 1
last = -1
for i, p, y in iPY:
    if p == last:
        cnt += 1
    else:
        last = p
        cnt = 1

    ans.append([i, str(p).zfill(6) + str(cnt).zfill(6)])

ans.sort()

for a in ans:
    print(a[1])

class Info:
  def __init__(self, num, p, y, id):
    self.num = num
    self.p = p
    self.y = y
    self.id = id
    
n, m = map(int, input().split())
info = [Info(0, 0, 0, '')]
for num in range(1, m + 1):
  p, y = map(int, input().split())
  info.append(Info(num, p, y, ''))

info = sorted(info, key=lambda x: (x.p, x.y))

cnt = 1
for i in range(1, m + 1):
  if info[i].p != info[i-1].p:
    cnt = 1
  else:
    cnt += 1
  info[i].id = "{0:06d}{1:06d}".format(info[i].p, cnt)

info = sorted(info, key=lambda x: x.num)
info.pop(0)

for x in info:
  print(x.id)

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

PY_sorted = sorted(PY, key=lambda a: (a[0], a[1]))
PY_sorted[0][3] = str(PY_sorted[0][0]).zfill(6) + str(1).zfill(6)
#print(PY_sorted)
cnt = 1
for i in range(1, M):
    cnt += 1
    if PY_sorted[i][0] != PY_sorted[i - 1][0]:
        cnt = 1
        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)
    else:
        PY_sorted[i][3] = str(PY_sorted[i][0]).zfill(6) + str(cnt).zfill(6)
#print(PY_sorted)
ans = sorted(PY_sorted, key=lambda a: a[2])
for a in ans:
    print((a[3]))



import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return list(map(int, input().split()))
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,m = i_map()
    l = []
    for i in range(m):
        p,y = i_map()
        l.append([i,p,y,0])

    l.sort(key = lambda x :(x[1], x[2]))
    ken = l[0][1]
    cnt = 1

    for i in l:
        if i[1] == ken:
            i[3] = cnt
            cnt += 1
        else:
            i[3] = 1
            cnt = 2
            ken = i[1]
    l.sort(key = lambda x:x[0])

    ans = []
    for i in l:
        ans.append(str(i[1]).zfill(6) + str(i[3]).zfill(6))
    for i in ans:
        print(i)

def __starting_point():
    main()

__starting_point()

n,m=map(int,input().split())
c=[[] for _ in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    c[p-1].append([i,y])
ans=[0]*m
for i in range(n):
    c[i].sort(key=lambda x:x[1])
    for j in range(len(c[i])):
        ID=str(i+1).zfill(6)+str(j+1).zfill(6)
        ans[c[i][j][0]]=ID
print(*ans,sep="\n")

n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
b = [[] for _ in range(n+1)]
for i in range(m):
    b[a[i][0]].append((a[i][1],i+1))
#print(b)
for i in range(1,n+1):
    b[i].sort()
ans = ["."]*m
for i in range(1,n+1):
    for j in range(len(b[i])):
        ans[b[i][j][1]-1] = "0"*(6-len(str(i))) + str(i) + "0"*(6-len(str(j+1))) + str(j+1)
print(*ans, sep="\n")

def main():
    import bisect
    n,m = list(map(int,input().split()))
    d = [[] for i in range(n)]
    ans = [0 for i in range(m)]
    for i in range(m):
        p,y = list(map(int,input().split()))
        d[p-1].append((y,i))
    for i,d_ in enumerate(d):
        d_.sort()
        for c, d__ in enumerate(d_):
            ans[d__[1]] = str(i+1).zfill(6) + str(c+1).zfill(6)
    for i in range(m):
        print((ans[i]))

def __starting_point():
    main()

__starting_point()

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

no = {}
ken = [[] for i in range(N)]
for i in range(M):
    p, y = list(map(int, input().split()))
    no[i] = str(p)+'_'+str(y)
    ken[p-1].append(y)

ans = {}
for i in range(N):
    ken[i].sort()
    for j in range(len(ken[i])):
        ans[str(i+1)+'_'+str(ken[i][j])] = str(i+1).zfill(6) + str(j+1).zfill(6)

for i in range(M):
    print((ans[no[i]]))


n, m = list(map(int, input().split()))
city = []

for i in range(m):
    a = list(map(int, input().split()))+[i]
    city.append(a)
city.sort(key=lambda x: x[1])

count = [1 for _ in range(n)]
for k in range(m):
    city[k].append(count[city[k][0]-1])
    count[city[k][0]-1] += 1
city.sort(key=lambda x: x[2])

for i in city:
    print((str(i[0]).zfill(6)+str(i[-1]).zfill(6)))


n,m = map(int,input().split())
L = []
for i in range(m):
    li = list(map(int,input().split()))
    L.append(li)

li = []
for i,j in enumerate(L):
    li.append(j+[i])
li.sort(key = lambda x:(x[0],x[1]))

li.append([0,0,0])

k,r = li[0][0],1
for i in range(m):
    if li[i][0] == k:
        if li[i+1][1] == li[i][1]:
            li[i][1] = r
            li[i+1][1] = r
        else:
            li[i][1] = r
            r +=1
    else:
        k = li[i][0]
        r = 1
        li[i][1] = r
        r +=1

li.pop()

li.sort(key = lambda x:x[2])

for i in range(m):
    print("{:06d}".format(li[i][0])+"{:06d}".format(li[i][1]))

from bisect import bisect_left
n,m = map(int, input().split())

l = [[] for _ in range(n)]
city = []
for i in range(m):
  p,y = map(int, input().split())
  city.append([p,y])
  l[p-1].append(y)

for i in l: i.sort()
for i in city:
  ans = ""
  ans += "0"*(6-len(str(i[0])))+str(i[0])
  t = str(bisect_left(l[i[0]-1], i[1]) + 1)
  ans += "0"*(6-len(t))+t
  print(ans)

n,m=map(int, input().split())
alist=[]
for i in range(m):
  p,y=map(int, input().split())
  alist.append([i+1,p,y])
alist.sort(key=lambda x: x[2])
blist=[0]*(n+1)
ans=[0]*m
for i in range(m):
  blist[alist[i][1]]+=1
  ans1='0'*(6-len(str(alist[i][1])))
  ans2=str(alist[i][1])
  ans3='0'*(6-len(str(blist[alist[i][1]])))
  ans4=str(blist[alist[i][1]])
  ans[alist[i][0]-1]=ans1+ans2+ans3+ans4
for i in range(m):
  print(ans[i])

N,M = list(map(int,input().split()))
D = [[]for _ in range(N)]#元の入力順と設立年数を県ごとに保持するリスト

for i in range(M):
    p,y = list(map(int,input().split()))
    D[p-1].append((y,i))
ans = [0]*M
#print(D)

for i,d in enumerate(D):
    #print(i,d)
    d.sort()
    for k,(y,j)in enumerate(d):
        #print(k,(y,j))
        ans[j]=str(i+1).zfill(6)+str(k+1).zfill(6)

print(('\n'.join(ans)))




N,M=map(int,input().split())
py=[list(map(int,input().split()))for _ in range(M)]
epy=list(enumerate(py))
P=[[]for _ in range(N+1)]
for x in epy:
    P[x[1][0]].append(x)

i=1
ans=[]
while i<=N:
    L=P[i]
    L.sort(key=lambda x:x[1])
    j=0
    while j<len(L):
        L[j][1][1]=j+1
        ans.append(L[j])
        j+=1
    i+=1
ans.sort()

for e,py in ans:
    p,y=map(str,py)
    p='0'*(6-len(p))+p
    y='0'*(6-len(y))+y
    print(p+y)

n,m=list(map(int,input().split()))
ken=[1 for i in range(n+1)]
inf=[[] for i in range(m)]
def f(x):
    m=0
    while x>0:
        m+=1
        x=x//10
    return m

for i in range(m):
    p,y=list(map(int,input().split()))
    inf[i].append(i+1)
    inf[i].append(p)
    inf[i].append(y)
inf=sorted(inf, key=lambda x: x[2])

for i in range(m):
    inf[i].append(ken[inf[i][1]])
    ken[inf[i][1]]+=1
inf=sorted(inf)


for i in range(m):
    ans=""
    p=inf[i][1]
    y=inf[i][3]
    for j in range(6-f(p)):
        ans+="0"
    ans=ans+str(p)
    
    for j in range(6-f(y)):
        ans=ans+"0"
    ans=ans+str(y)
    print(ans)
    
    
    
    
    



    
        
        
        
          


N,M=map(int,input().split())
A=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  A[a-1].append((b,i))
ans=[0]*M
for i in range(N):
  d=sorted(A[i])
  n=len(d)
  for j in range(n):
    a,b=d[j]
    D=str(i+1)
    E=str(j+1)
    r=D.zfill(6)+E.zfill(6)
    ans[b]=r
for i in ans:
  print(i)

import numpy as np

N,M=map(int,input().strip().split())
PY=np.array([list(map(int,input().strip().split())) for _ in range(M)])

l=[[] for n in range(N)]
for m in range(M):
    l[PY[m,0]-1].append(PY[m,1])

dp={}
for n in range(N):
    if l[n]:
        l[n].sort()
        for i in range(len(l[n])):
            city="000000"+str(n+1)
            num="000000"+str(i+1)
            dp[(n,l[n][i]-1)]=str(city[-6:]+num[-6:])
for m in range(M):
    print(dp[(PY[m,0]-1,PY[m,1]-1)])

n, m = list(map(int, input().split()))
cities = []

for i in range(m):
    p, y = list(map(int, input().split()))
    cities.append([p, y, i])

sorted_cities = sorted(cities, key=lambda x: (x[0], x[1]))
cnt = 1
ans = []
for i in range(m-1):
    p_id = str(sorted_cities[i][0]).rjust(6, '0')
    c_id = str(cnt).rjust(6, '0')
    ans.append([sorted_cities[i][2], p_id+c_id])
    if sorted_cities[i][0] != sorted_cities[i+1][0]:
        cnt = 1
    else:
        cnt += 1

p_id = str(sorted_cities[m-1][0]).rjust(6, '0')
c_id = str(cnt).rjust(6, '0')
ans.append([sorted_cities[m-1][2], p_id+c_id])
ans.sort()

for id in ans:
    print((id[1]))



from collections import defaultdict
from bisect import bisect

N, M = list(map(int, input().split()))
p = [tuple(map(int, input().split())) for _ in range(M)]
a = defaultdict(list)
for x, y in sorted(p):
    a[x] += [y]

for x, y in p:
    z = bisect(a[x], y)
    print(("%06d%06d"%(x, z)))


n, m = map(int, input().split())

P = []
Y = []
I = []
for i in range(m):
    a, b = map(int, input().split())
    P.append(a)
    Y.append(b)
    I.append(i)

Z = zip(P, Y, I)
Z = sorted(Z)
P, Y, I = zip(*Z)

N = []
c = P[0]
d = 1
for i in range(m):
    if c == P[i]:
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1
    else:
        c = P[i]
        d = 1
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1

Z = zip(I, N)
Z = sorted(Z)
I, N = zip(*Z)
for i in N:
    print(i)

def main():
    n,m=map(int,input().split())
    l=[tuple(map(int,input().split())) for _ in range(m)]
    py=sorted(l, key=lambda x: (x[0],x[1]))
    d={}
    i = 1
    prev=0
    for p,y in py:
        if prev != p:
            i = 1
            prev = p
        d[(p,y)] = "{:0>6}".format(p)+"{:0>6}".format(i)
        i += 1
    for x in l:
        print(d[x])

def __starting_point():
    main()
__starting_point()

from collections import defaultdict
from bisect import bisect
n,m=map(int,input().split())
l=[tuple(map(int,input().split())) for _ in range(m)]
a=defaultdict(list)
for x,y in sorted(l):
    a[x]+=[y]

for x,y in l:
    z=bisect(a[x],y)
    print('%06d%06d'%(x,z))

n, m = list(map(int, input().split()))
ps = [[] for _ in range(n)]

for i in range(m):
    p, y = list(map(int, input().split()))
    ps[p-1].append((y, i))

for i in range(n):
    ps[i] = sorted(ps[i])

    pstr = str(i+1).zfill(6)

    for j in range(len(ps[i])):
        ps[i][j] = (pstr + str(j+1).zfill(6), ps[i][j][1])

ps = [city for sub in ps for city in sub]
ps = sorted(ps, key = lambda x: x[1])

for city in ps:
    print(city[0])

n,m = map(int,input().split())
l = [[] for i in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    l[i] = [a,b,i]
l = list(sorted(l,key=lambda x: (x[0], x[1])))
ans = [[] for i in range(m)]
x = 0
y = 1
for i in range(m):
    if x != l[i][0]:
        x = l[i][0]
        y = 1
    else:
        y += 1
    a = str(x).zfill(6)
    b = str(y).zfill(6)
    ans[i] = [a+b,l[i][2]]
ans = list(sorted(ans,key=lambda x: x[1]))
for i in range(m):
    print(ans[i][0])

# author:  Taichicchi
# created: 11.10.2020 10:28:32

import sys

n, m = list(map(int, input().split()))

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

ls.sort(key=lambda x: x[2])
d = dict(list(zip(list(range(1, n + 1)), [0 for i in range(n)])))


for i in range(m):
    ls[i].append(d[ls[i][1]] + 1)
    d[ls[i][1]] += 1
    ls[i].append(str(ls[i][1]).zfill(6) + str(ls[i][3]).zfill(6))

ls.sort(key=lambda x: x[0])

for l in ls:
    print((l[-1]))


n,m=map(int,input().split())
PY=[list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    PY[i].append(i)
py=sorted(PY)
ans=[None]*m
#print(py,PY)
tmp_y=1
for i in range(m):
    if i>0:
        if py[i][0]!=py[i-1][0]:
            tmp_y=1
        else:
            tmp_y+=1
    ans_l="0"*(6-len(str(py[i][0])))+str(py[i][0])
    ans_r="0"*(6-len(str(tmp_y)))+str(tmp_y)
    #print(ans_l+ans_r)
    ans[py[i][2]]=ans_l+ans_r
[print(i) for i in ans]

n, m = list(map(int, input().split()))
p_y = []
for i in range(m):
    p, y = list(map(int, input().split()))
    p_y.append([p, y, i])

p_y_sorted = sorted(p_y)
li_id = []
prev_p = -1
cnt = 1

for i in p_y_sorted:
    if(prev_p != i[0]):
        prev_p = i[0]
        cnt = 1
    id = str(i[0]).zfill(6) + str(cnt).zfill(6)
    li_id.append([i[2], id])
    cnt += 1

li_id_sorted = sorted(li_id)

for i in li_id_sorted:
    print((i[1]))



import bisect
n,m = map(int,input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
  s,t = map(int,input().split())
  p.append(s)
  y.append(t)
  x[s-1].append(t)
for i in range(n):
  x[i].sort()
  
for i in range(m):
  index = bisect.bisect_left(x[p[i]-1],y[i])
  print("{:06}{:06}".format(p[i],index+1))

n, m = list(map(int, input().split()))
city = [list(map(int, input().split())) for _ in range(m)]
pref = [[] for _ in range(n+1)]

ans = []

for i, c in enumerate(city):
    pref[c[0]].append([i, c[1]])

for i in range(n):
    pref[i + 1].sort(key=lambda x: x[1])
    for j in range(len(pref[i + 1])):
        ans.append([pref[i+1][j][0], str(i+1).zfill(6) + str(j+1).zfill(6)])

ans.sort(key=lambda x: x[0])

for c in ans:
    print((c[1]))


n, m = list(map(int, input().split()))

c = [0] * (n+1)

py = []

for i in range(m):
    py.append(list(map(int, input().split())) + [i])

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

a = [""] * m

for p, y, i in py:
    c[p] += 1
    x = c[p]
    z = str(p * 1000000 + x)
    #print(a)
    if len(z) < 12:
        a[i] = "0" * (12-len(z)) + z
    else:
        a[i] = z

for x in a:
    print(x)

n,m=list(map(int,input().split()))

ans=[]

re=[[] for _ in range(n)]



for _ in range(m):
  a=list(map(int,input().split()))
  re[a[0]-1].append(a[1])
  ans.append(a)
  
d={}
for f in re:
  new=sorted(f)
  
  for i in range(len(new)):
    d[new[i]]=i+1
  
for x in ans:
  p=x[0]
  q=d[x[1]]
  print((str('{:0=6}'.format(p))+str('{:0=6}'.format(q))))
  



N,M=list(map(int,input().split()))
numbers=[{} for n in range(N)]
for m in range(M):
    P,Y=list(map(int,input().split()))
    numbers[P-1][m]=Y
answers={}
for n in range(N):
    number=numbers[n]
    if len(number)==0:
        continue
    new_number=sorted(list(number.items()), key=lambda x:x[1])
    suuji=1
    for num in new_number:
        answers[num[0]]=(6-len(str(n+1)))*'0'+str(n+1)+(6-len(str(suuji)))*'0'+str(suuji)
        suuji+=1
answer=sorted(list(answers.items()), key=lambda x:x[0])
for ans in answer:
    print((ans[1]))


N, M = map(int, input().split())
cnt = [0]*N
history = []
res = ['']*M

for i in range(M):
    P, Y = map(int, input().split())
    history.append((Y, P - 1, i))

history.sort()

for i in range(M):
    cnt[history[i][1]] += 1
    res[history[i][2]] = str(history[i][1] + 1).zfill(6) + str(cnt[history[i][1]]).zfill(6)

for i in range(M):
    print(res[i])

n,m = map(int,input().split())
p_dict = {}
ans = []
for i in range(m):
    p,y = map(int,input().split())
    if p not in p_dict.keys():
        p_dict[p] = [[y,p,i]]
    else:
        p_dict[p].append([y,p,i])

for p in p_dict.keys():
    p_dict[p].sort()
    for i in range(len(p_dict[p])):
        p_dict[p][i].append(i+1)
        ans.append(p_dict[p][i])

ans.sort(key=lambda x: x[2])  
for y, p, oi, si in ans:  
    print("{:06d}{:06d}".format(p, si)) 

def digit6(n):
  return ("000000" + str(n))[-6:]

def main():
  N, M = list(map(lambda n: int(n), input().split(" ")))
  CITY = []
  for i in range(M):
    tmp = input().split(" ")
    CITY.append({
      "pref": int(tmp[0]),
      "year": int(tmp[1]),
      "no": i + 1
    })
    
  CITY.sort(key=lambda c: (c["pref"], c["year"]))
  
  order = 0
  pref = ""
  for c in CITY:
    if pref != c["pref"]:
      pref = c["pref"]
      order = 1
    else:
      order += 1
    c["id"] = digit6(pref) + digit6(order)
  
  CITY.sort(key=lambda c: c["no"])
  for i in range(len(CITY)):
    print(CITY[i]["id"])
      
    
  
main()

N,M=list(map(int,input().split()))
PY=[[list(map(int,input().split())),i] for i in range(M)]
PY.sort()
cnt=[0 for i in range(N+1)]
ans=[]
for i in range(M):
    cnt[PY[i][0][0]]+=1
    ans.append([PY[i][1],str(PY[i][0][0]).zfill(6)+str(cnt[PY[i][0][0]]).zfill(6)])
ans.sort()
for i in range(M):
    print((ans[i][1]))


n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]
di = []
for i in range(m):
    a,b = map(int,input().split())
    ls[a].append([b,i+1])
for j in range(n+1):
    if ls[j] != []:
        ls[j].sort(key=lambda x :x[0])
        for k in range(len(ls[j])):
            di.append([ls[j][k][1],str(10**12+j*10**6+k+1)[1:]])
di.sort(key=lambda x :x[0])
for l in range(m):
    print(di[l][1])

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, M, PY):
    ken = [0] * (N + 1)
    PY = [PY[i] + [i] for i in range(M)]
    PY.sort(key=lambda x: x[1])
    for i in range(M):
        p, y, s = PY[i]
        ken[p] += 1
        PY[i].append(ken[p])
    PY.sort(key=lambda x: x[2])
    for p, y, s, n in PY:
        print((('000000' + str(p))[-6:] + ('000000' + str(n))[-6:]))


def __starting_point():
    N, M = list(map(int, input().split()))
    PY = [[int(i) for i in input().split()] for _ in range(M)]
    solve(N, M, PY)

    # # test
    # from random import randint, sample
    # from func import random_str
    # N, M = 10 ** 5, 10 ** 5
    # PY = sample([[randint(1, 5), 10 ** 8 - i] for i in range(M)], M)
    # solve(N, M, PY)

__starting_point()

#!/usr/bin/env python3
(n, m), *q = [[*list(map(int, i.split()))] for i in open(0)]
s = sorted(q)
d = {}
for k, v in s:
    if k not in d:
        d[k] = []
    d[k].append(v)
c = {}
for k, v in list(d.items()):
    i = 0
    if k not in c:
        c[k] = {}
    while i < len(v):
        i += 1
        c[k][v[~-i]] = str(i)
for p, y in q:
    pn = "00000" + str(p)
    cn = "00000" + c[p][y]
    print((pn[-6:] + cn[-6:]))


N,M=map(int,input().split())
d={}
PY=[]
import bisect
for _ in range(M):
    p,y=map(int,input().split())
    PY.append((p,y))
    t=d.get(p, [0])
    i=bisect.bisect_left(t,y)
    t.insert(i,y)
    d[p]=t
    
dx={}
for k, v in d.items():
    for i in range(len(v)):
        dx[(k,v[i])]=i
        
for p,y in PY:
    print(str(p).zfill(6)+str(dx[(p,y)]).zfill(6))

from operator import itemgetter

n, m = map(int, input().split())
yp = []
for i in range(m):
  p_, y_ = map(int, input().split())
  yp.append([y_, p_, i+1])
py = sorted(yp)
ken = [0]*n
res = []
for i in range(m):
  ken[py[i][1]-1] += 1
  p, q, r = py[i][1], ken[py[i][1]-1], py[i][2]
  res.append([p, q, r])
#print(yp)
#print(py)

res.sort(key=itemgetter(2))
#print(res)
for i in range(m):
  ans1 = [0]*(6-len(str(res[i][0])))
  ans1.append(res[i][0])
  ans2 = [0]*(6-len(str(res[i][1])))
  ans2.append(res[i][1])
  print(*ans1, *ans2, sep='')

n,m = map(int,input().split())
a = []
for i in range(m):
    x,y = map(int,input().split())
    a.append([x,y])
b = a.copy()
c = sorted(b, key=lambda x:(x[0],x[1]))
d = [{}for i in range(10**5+1)]
count = 1
s = '%d' % c[0][0]
s = s.zfill(6)
s2 = '%d' % count
s2 = s2.zfill(6)

d1 = {c[0][1]:s+s2}
for i in range(1,m):
    if c[i][0] == c[i-1][0]:
        count +=1
        s2 = '%d' % count
        s2 = s2.zfill(6)
        d1[c[i][1]] = s+s2
    else:
        d[c[i-1][0]] = d1
        count = 1
        s = '%d' % c[i][0]
        s = s.zfill(6)
        s2 = '%d' % count
        s2 = s2.zfill(6)
        d1 = {c[i][1]:s+s2}
d[c[-1][0]] = (d1)
for i in range(m):
    d2 = d[a[i][0]]
    print(d2.get(a[i][1]))