Problem:
 Score: 300 points    Problem Statement 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 1 2 3
1 32
2 63
1 12      Sample Output 1 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 .        Sample Input 2 2 3
2 55
2 77
2 99      Sample Output 2 000002000001
000002000002
000002000003

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        
    return n,m,g

def main():
    n,m=inpm()
    py=[]
    num=[1 for _ in range(n)]
    for i in range(m):
        p,y=inpm()
        py.append([y,p,i])
    py.sort()
    ans=[]
    for i in range(m):
        ID_head=list(str(py[i][1]))
        ID_back=list(str(num[py[i][1]-1]))
        num[py[i][1]-1]+=1
        if len(ID_head)<6:
            ID_head=['0' for _ in range(6-len(ID_head))] + ID_head
        if len(ID_back)<6:
            ID_back=['0' for _ in range(6-len(ID_back))] + ID_back
        ID=ID_head+ID_back
        ans.append( [ py[i][2] , ID ] )
    ans.sort()
    for i in range(m):
        print(''.join(ans[i][1]))
        
if __name__ == "__main__":
    main()

Solution (Python):
from itertools import groupby
from operator import itemgetter
N, M = map(int, input().split())
IPY = []
for i in range(M):
    p, y = map(int, input().split())
    IPY.append([i, p, y])
IPY.sort(key=itemgetter(1, 2))
Ans = [-1] * M
for v, g in groupby(IPY, key=itemgetter(1)):
    for i, (idx, p, y) in enumerate(g, 1):
        Ans[idx] = "{:06d}{:06d}".format(p, i)
print("\n".join(Ans))

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
PY =[]
for i in range(M):
    P,Y = map(int,input().split())
    PY.append([i,P,Y])
PY.sort(key=lambda x:x[2])
PY.sort(key=lambda x:x[1])
lis = [0]*M
tmp = 0
num = 1
for ind,j in enumerate(PY):
    if j[1] == tmp:
        num += 1
        PY[ind][2] = num
        tmp = PY[ind][1]
    else:
        num = 1
        PY[ind][2] = num
        tmp = PY[ind][1]
PY.sort(key=lambda x: x[0])
for i in range(M):
    prt1 = str(1000000+PY[i][1])
    prt2 = str(1000000+PY[i][2])
    print(prt1[1:]+prt2[1:])

Solution (Python):
n,m = map(int,input().split())

pyl = []
pyl2 = [[] for i in range(n)]    
for i in range(m):
    p,y = map(int,input().split())
    pyl.append((p,y))
    pyl2[p-1].append((y,i))
    
argsortpyl = []
for p in pyl2:
    argsortpyl.append(sorted(p))
    

ansl = ["" for i in range(m)]

for idx, py in enumerate(argsortpyl):
    for ud,(y,i) in enumerate(py):
        ansl[i] = (idx+1, ud+1)
        
for x,y in ansl:
    print(str(x).zfill(6) + str(y).zfill(6))

Solution (Python):
def main():
    n,m = map(int,input().split())
    l = [[] for _ in range(n+1)]
    lp = []
    for i in range(m):
        p,y = map(int,input().split())
        l[p].append([i,y])
        lp.append(p)
    
    for p in l:
        p.sort(key=lambda x: x[1])
        for no in range(0,len(p)):
            p[no].append(no+1)
        p.sort()

    pidx = [0 for x in range(n+1)]
    for p in lp:
        print("{:06}{:06}".format(p,l[p][pidx[p]][2]))
        pidx[p] += 1

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n,m = map(int,input().split())
    l = []
    for i in range(m):
        l.append([i] + list(map(int,input().split())))

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

    p = -1
    no = 0
    for item in l:
        if item[1] != p:
            p = item[1]
            no = 1
        else:
            no += 1
        item.append(no)

    l.sort()

    for item in l:
        print("{:06}{:06}".format(item[1],item[3]))

if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
l = []
for i in range(m):
    l.append([i] + list(map(int,input().split())))

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

p = -1
no = 0
for item in l:
    if item[1] != p:
        p = item[1]
        no = 1
    else:
        no += 1
    item.append(no)

l.sort()

for item in l:
    print("{:06}{:06}".format(item[1],item[3]))

Solution (Python):

import sys


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    py_list = []
    x = 0
    for m in range(M):
        py_list.append([P[m], Y[m], m, x])

    
    py_list = sorted(py_list)

    
    x = 1
    for m in range(M):
        p_i = py_list[m][0]
        if m != 0 and py_list[m-1][0] != py_list[m][0]:
            x = 1
        py_list[m][3] = x
        x += 1

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

    for m in range(M):
        p = py_list[m][0]
        x = py_list[m][3]
        print("{:06}".format(p) + "{:06}".format(x))
    

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    P = [int()] * (M)  
    Y = [int()] * (M)  
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, M, P, Y)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
pref_dict = {}

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

sorted_dict = sorted(pref_dict.items(), key= lambda x: (x[1][0], x[1],[1]))
ans_dict = {}
buf = ""
count = 1

for tup in sorted_dict:

    row = tup[0]
    pref_name = "00000{}".format(tup[1][0])
    pref_name = pref_name[-6:]

    if pref_name == buf:
        count += 1
    else:
        count = 1

    pref_id = "00000{}".format(count)
    pref_id = pref_id[-6:]
    ans_dict[row] = [pref_name, pref_id]
    buf = pref_name

for key, value in sorted(ans_dict.items(), key=lambda x: x[0]):
    print(*value, sep="")

Solution (Python):
N, M = map(int, input().split())
pref_dict = {}

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

sorted_dict = sorted(pref_dict.items(), key= lambda x: (x[1][0], x[1],[1]))
ans_dict = {}
buf = ""
count = 1

for tup in sorted_dict:

    row = tup[0]
    pref_name = "00000{}".format(tup[1][0])
    pref_name = pref_name[-6:]

    if pref_name == buf:
        count += 1
    else:
        count = 1

    pref_id = "00000{}".format(count)
    pref_id = pref_id[-6:]
    ans_dict[row] = [pref_name, pref_id]
    buf = pref_name

for key, value in sorted(ans_dict.items(), key=lambda x: x[0]):
    print(*value, sep="")

Solution (Python):
n,m=map(int,input().split())
lst=[]
for i in range(m):
  p,y=map(int,input().split())
  lst.append([i,p,y])
lst.sort(key=lambda x:(x[1],x[2]))
j=1
Lst=[]
for i in range(m):
  if lst[i][1]==lst[min(m-1,i+1)][1]:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j+=1
    Lst.append([lst[i][0],u])
  else:
    s=str(lst[i][1])
    t=str(j)
    u=s.zfill(6)+t.zfill(6)
    j-=j-1
    Lst.append([lst[i][0],u])
Lst.sort(key=lambda x:x[0])
for k in range(m):
  print(Lst[k][1])

Solution (Python):
N, M = map(int, input().split())
C = [list(map(int, input().split())) for i in range(M)]
D = [0 for i in range(max(C[i][0] for i in range(M)))]
for i in range(M):
  C[i].append(i)
  C[i][0], C[i][1] = C[i][1], C[i][0]
C.sort()
for i in range(M):
  D[C[i][1]-1] += 1
  C[i].append('{}'.format(C[i][1] * 1000000 + D[C[i][1]-1]))
  if len(C[i][3]) != 12:
    for x in range(12-len(C[i][3])):
      C[i][3] = '0' + C[i][3]
  C[i][0] = C[i][2]
  
C.sort()
for i in range(len(C)):
  print(C[i][3])

Solution (Python):
N, M = map(int,input().split())
array = []
ans = []
for i in range(M):
    array.append(list(map(int, input().split()))+[i])
array.sort()
count = 1
for i in range(M):
    id_left = str(array[i][0])
    while len(id_left) < 6:
        id_left = '0' + id_left
    id_right = str(count)
    while len(id_right) < 6:
        id_right = '0' + id_right
    id = id_left + id_right
    ans.append([array[i][2],id])
    if i == M-1:
        break
    if array[i][0] != array[i+1][0]:
        count = 1
    else:
        count += 1
ans.sort()
for i in ans:
    print(i[1])

Solution (Python):

import sys

import math







from copy import deepcopy

def main():
    n, m = (int(x) for x in sys.stdin.readline().split())
    PY = [[int(x) for x in sys.stdin.readline().split()] for _ in range(m)]
    py = sorted(deepcopy(PY))

    ids = dict()
    for i in range(m):
        p, y = py[i][0], py[i][1]
        if not p in ids:
            ids[p] = dict()
            x = 0
        x += 1
        id_i = '0' * (6 - (math.floor(math.log10(p)) + 1)) + str(p) + '0' * (6 - (math.floor(math.log10(x)) + 1)) + str(x)
        ids[p][y] = id_i
    
    for i in range(m):
        p, y = PY[i][0], PY[i][1]
        print(ids[p][y])


if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
A=[[] for i in range(n+1)]
I=[]
for i in range(m):
    p,y=map(int,input().split())
    A[p].append([i,y])

for i in range(n+1):A[i].sort(key=lambda x: x[1])

for i in range(n+1):
    if A[i] != []:
        for j in range(len(A[i])):
            I.append([A[i][j][0] ,str(i).zfill(6) ,str(j+1).zfill(6)])
I.sort(key=lambda x: x[0])
for i in range(len(I)):print(I[i][1],I[i][2],sep="")

Solution (Python):
n, m = map(int, input().split())
L = []
for i in range(m):
  L.append([i] + list(map(int, input().split() + ["000000000000"])))
L.sort(key=lambda x:(x[1], x[2]))


counter = 1
city = 0
for i in range(m):
  if city == L[i][1]:
    counter += 1
  else:
    counter = 1
  L[i][3] = str(L[i][1]).zfill(6) + str(counter).zfill(6)
  city = L[i][1]

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

Solution (Python):
N , M = map(int,input().split())
birth = []
for i in range(M):
    a , b = map(int,input().split())
    birth.append([a,b,i])

work_list = sorted(birth,key=lambda x: x[1])
work_list.sort()

lower = 1
ans = []
for i in range(1,len(birth)):
    ans.append([work_list[i-1][2],str(work_list[i-1][0]).zfill(6) + str(lower).zfill(6)])
    if work_list[i][0] == work_list[i-1][0]:
        lower += 1
    else:
        lower = 1
ans.append([work_list[M - 1][2],str(work_list[M-1][0]).zfill(6) + str(lower).zfill(6)])
ans.sort()
for val in ans:
    print(val[1])

Solution (Python):
from sys import stdin
import bisect

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

lin = [[]for _ in range(n)]
lin2 = []

for i in range(m):
    lin[li[i][0]-1].append(li[i][1])

for j in range(n):
    liv = sorted(lin[j])
    lin2.append(liv)

for k in range(m):
    tosi = str(li[k][0]).zfill(6)
    ban =  str(bisect.bisect(lin2[li[k][0]-1],li[k][1])).zfill(6)
    print(tosi+ban)

Solution (Python):
from sys import stdin
import bisect

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

lin = [[]for i in range(n)]
lin2 = []
li3 = []
for j in range(m):
    lin[li[j][0]-1].append(li[j][1])
    lin2.append(li[j][0]-1)

for j in range(n):
    liv = sorted(lin[j])
    li3.append(liv)

for k in range(m):
    tosi = str(li[k][0]).zfill(6)
    ban =  str(bisect.bisect(li3[li[k][0]-1],li[k][1])).zfill(6)
    print(tosi+ban)

Solution (Python):
from collections import defaultdict
import bisect
n,m=map(int,input().split())
PY=[list(map(int,input().split())) for _ in range(m)]
d=defaultdict(list)
for py in sorted(PY):
  d[py[0]].append(py[1])
for p, y in PY:
  print(str(p).zfill(6)+str(bisect.bisect_left(d[p],y)+1).zfill(6))

Solution (Python):
n, m = map(int, input().split())
lst = [[] for _ in range(n + 1)]
py = [None] * m
for i in range(m):
    p, y = map(int, input().split())
    py[i] = [p, y]
    lst[p].append(y)

for i in range(n + 1):
    lst[i] = {v: i for i, v in enumerate(sorted(lst[i]))}

for i, j in py:
    print(str(i).zfill(6) + str(lst[i][j]+1).zfill(6))

Solution (Python):
n,m= map(int, input().split())
x=[[] for j in range(n)]
for i in range(m):
    p,ye= map(int, input().split())
    x[p-1].append([ye,i])
for i in range(n):
    x[i].sort()
y=[0]*m
cnt=1
for i in range(n):
    for a in range(len(x[i])):
        j=str(i+1)
        k=str(cnt)
        y[x[i][a][1]]="0"*(6-len(j))+j+"0"*(6-len(k))+k
        cnt+=1
    cnt=1
for i in range(m):
    print(y[i])

Solution (Python):
from operator import itemgetter

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

x = [0] * n
pn = [i for i in range(1, m+1)]
idn = [''] * m

yp = list(zip(y, p, pn))
yp.sort()

for i in range(m):
    p_ = yp[i][1] - 1
    x[p_] += 1
    idn[i] = format(yp[i][1], '0>6') + format(x[p_], '0>6')

y, p, pn = zip(*yp)
yp = list(zip(y, p, pn, idn))
yp.sort(key=itemgetter(2))
for i in range(m):
    print(yp[i][3])

Solution (Python):
n,m = map(int,input().split())
s = [[] for _ in range(n+1)]
for i in range(m):
    p,y = map(int,input().split())
    s[p].append([y,i])
ans = [0]*m
for p in range(1,n+1):
    cnt = 1
    for (y,i) in sorted(s[p]):
        ans[i] = '{:06}{:06}'.format(p,cnt)
        cnt += 1
for j in range(len(ans)):
    print(ans[j])

Solution (Python):

import sys
from bisect import bisect_left, bisect_right

N,M=map(int, sys.stdin.readline().split())
P=[ [] for _ in range(N+1) ]  
Q=[]    

for _ in range(M):
    p,y=map(int, sys.stdin.readline().split())
    P[p].append(y)
    Q.append((p,y))

for i in range(1,N+1):
    P[i].sort()

for p,y in Q:
    print str(p).zfill(6)+str(bisect_left(P[p],y)+1).zfill(6)

Solution (Python):

import sys
from bisect import bisect_left, bisect_right

N,M=map(int, sys.stdin.readline().split())
P=[ [] for _ in range(N+1) ]  
Q=[]    

for _ in range(M):
    p,y=map(int, sys.stdin.readline().split())
    P[p].append(y)
    Q.append((p,y))

for i in range(1,N+1):
    P[i].sort()

for i,y in Q:
    print str(i).zfill(6)+str(bisect_left(P[i],y)+1).zfill(6)

Solution (Python):
N,M=map(int, input().split())
e =[]
for i in range(M):
  p,y = map(int, input().split())
  e.append([p,y,i])
e.sort()

count =1
pre = e[0][0]
for i in e:
  if pre != i[0]:
    count = 1
  i.append(format(str(i[0]), '0>6')+format(str(count), '0>6'))
  count += 1
  pre = i[0]
  
e.sort(key = lambda x:x[2])

for i in e:
  print(i[3])

Solution (Python):
n, m = map(int, input().split())
py = []
for i in range(m):
	a = list(map(int, input().split()))
	py.append([a[0], a[1], i])
py.sort()

num = []
ken = py[0][0]
x = 0
for i in range(m):
	if py[i][0] == ken:
		x += 1
		spl = ['0' for i in range(6-len(str(py[i][0])))]
		sxl = ['0' for i in range(6-len(str(x)))]
		sp = ''.join(spl)
		sx = ''.join(sxl)
		s = sp+str(py[i][0])+sx+str(x)
		num.append([py[i][2], s])
	else:
		ken = py[i][0]
		x = 1
		spl = ['0' for i in range(6-len(str(py[i][0])))]
		sxl = ['0' for i in range(6-len(str(x)))]
		sp = ''.join(spl)
		sx = ''.join(sxl)
		s = sp+str(py[i][0])+sx+str(x)
		num.append([py[i][2], s])
num.sort()
for i in range(m):
	print(num[i][1])

Solution (Python):
N, M = map(int, input().split())
P, Y, P_new, P_Y = [], [], [], []
for _ in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)

for p in P:
    p_dig = len(str(p))
    add_0 = 6- p_dig
    P_new.append('0'*add_0 + str(p))
for m in range(M):
  temp =[]
  temp += [P_new[m], Y[m], m+1]
  P_Y.append(temp)
  
P_Y = sorted(P_Y, key=lambda x:(x[0], x[1]))
P_Y[0].append(1)

num = 1
for m in range(1,M):
    if P_Y[m][0] == P_Y[m-1][0]:
        num = num + 1
        P_Y[m].append(num)
    else:
        num = 1
        P_Y[m].append(num)

for m in range(M):
    n_dig = len(str(P_Y[m][3]))
    add_0 = 6- n_dig
    P_Y[m].append('0'*add_0 + str(P_Y[m][3]))
    P_Y[m].append(P_Y[m][0] + P_Y[m][4])

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

for m in range(M):
    print(P_Y[m][5])

Solution (Python):
from bisect import bisect_left
N, M = [int(x) for x in input().split()]
PY_list = [[int(x)-1 for x in input().split()] for _ in range(M)]
lst = [[] for _ in range(N)] 
for P, Y in PY_list:
    lst[P].append(Y)
for l in lst:
    l.sort()
for p, y in PY_list:
    print('{:06}{:06}'.format(p+1, bisect_left(lst[p], y)+1))

Solution (Python):
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)

Solution (Python):
n,m=map(int,input().split())
si=[list(map(int,input().split())) for i in range(m)]



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


sicount=[0]*n


for i in range(m):
  nanbanme=sicount[si[i][0]-1]+1
  sicount[si[i][0]-1]+=1
  ninsiki=str(si[i][0]).zfill(6)+str(nanbanme).zfill(6)
  si[i].append(ninsiki)

from operator import itemgetter

si=sorted(si,key=itemgetter(2))
for i in si:
  print(i[3])

Solution (Python):
N, M = map(int, input().split())
d = [[] for _ in range(N+1)]
for i in range(M):
    P, Y = map(int, input().split())
    d[P].append((Y, i))

dd = [""] * M

for P in range(1, N + 1):
    j = 1
    for (Y, i) in sorted(d[P]): 
        dd[i] = '{:06}{:06}'.format(P, j)
        j += 1
print(*dd, sep="\n")

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
bn = [[int(i) for i in input().split()]+[j] for j in range(m)]
ans = [0]*m
bn.sort()
temp = 0
cnt = 0

for i in bn:
  if temp == i[0]:
    cnt += 1
    ans[i[2]] = '%06d%06d' % (temp,cnt)
  else:
    temp = i[0]
    cnt = 1
    ans[i[2]] = '%06d%06d' % (temp,cnt)   
for j in ans:
  print(j)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
bn = [[int(i) for i in input().split()]+[j] for j in range(m)]
ans = [0]*m
bn.sort()
temp = 0
cnt = 0

for i in bn:
  if temp == i[0]:
    cnt += 1
    ans[i[2]] = str(temp * 1000000 + cnt).zfill(12)
  else:
    temp = i[0]
    cnt = 1
    ans[i[2]] = str(temp * 1000000 + cnt).zfill(12)    
for j in ans:
  print(j)

Solution (Python):
N, M = map(int, input().split())
PY = [[int(i) for i in input().split()] for _ in range(M)]

iPY = []
for i, (P, Y) in enumerate(PY) :
    iPY.append((i, P, Y))
iPY.sort(key=lambda x: x[2])

ret = [0] * M
counter = [0] * N
for i, P, _ in iPY :
    counter[P-1] += 1
    ret[i] = '{:06d}'.format(P) + '{:06d}'.format(counter[P-1])

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

Solution (Python):
from collections import defaultdict
import bisect

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

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

arr = [0] * m
for k, v in d.items():
    for i, item in enumerate(sorted(v, key=lambda x: x[0])):
        arr[item[1]] = (k, i)

for k, v in arr:
    print('{:06d}{:06d}'.format(k, v + 1))

Solution (Python):
from collections import defaultdict
from bisect import bisect

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

a = defaultdict(list)

for p_i in sorted(p):
  a[p_i[0]].append(p_i[1])
  
for p_i in p:
  x = p_i[0]
  y = bisect(a[x], p_i[1])
  
  print(str(x).zfill(6), str(y).zfill(6), sep='')

Solution (Python):
N,M = map(int,input().split())

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

for i in range(M):
  L[i].append(i + 1)

sortL = sorted(L)

ID = ""

order = 0

for i in range(0,len(L)):
  if sortL[i][0] > sortL[i-1][0]:
    order = 0
  order += 1
  pref = str(sortL[i][0])
  ID = "0" *  (6 - len(pref))
  ID += pref
  ID += "0" * (6 - len(str(order)))
  ID += str(order)
  sortL[i].append(ID)

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

for i in range(0,len(L)):
  print(sortL[i][-1])

Solution (Python):
N, M = map(int,input().split())
PY = [list(map(int,input().split())) for i in range(M)]
for i in range(M):
    PY[i].append(i)
PY.sort()
cnt = 1
ken = 0
for i in range(M):
    if i != 0:
        if PY[i][0]!=PY[i-1][0]:
            cnt = 1
        else: cnt += 1
    PY[i].append("0"*(6-len(str(PY[i][0])))+str(PY[i][0])+"0"*(6-len(str(cnt)))+str(cnt))
ans = sorted(PY, key =lambda x:x[2])
for i in range(M):
    print(ans[i][3])

Solution (Python):
import sys
input=sys.stdin.readline

N, M = [int(i) for i in input().split(" ")]
p = list()
y = list()
yd = {}
for i in range(0, M):
    pi, yi = [int(i) for i in input().split(" ")]
    p.append(pi)
    y.append(yi)
    if pi in yd.keys():
        yd[pi].append(yi)
    else:
        yd[pi] = [yi]

ydid = {}
for i in yd.keys():
    num = 1
    for j in sorted(yd[i]):
        ydid[j] = num
        num = num + 1

for i in range(0, M):
    print("{:06}{:06}".format(p[i], ydid[y[i]]))

Solution (Python):
N, M = [int(i) for i in input().split(" ")]
p = list()
y = list()
yd = {}
for i in range(0, M):
    pi, yi = [int(i) for i in input().split(" ")]
    p.append(pi)
    y.append(yi)
    if pi in yd.keys():
        yd[pi].append(yi)
    else:
        yd[pi] = [yi]

ydid = {}
for i in yd.keys():
    num = 1
    for j in sorted(yd[i]):
        ydid[j] = num
        num = num + 1

for i in range(0, M):
    print("{:06}{:06}".format(p[i], ydid[y[i]]))

Solution (Python):
N, M = [int(s) for s in input().split(' ')]
PY = []
PYsorted = []
for m in range(1, M + 1):
    p, y = [int(s) for s in input().split(' ')]
    PY.append((p, y))
    PYsorted.append((p, y))

PYsorted.sort(key=(lambda x: x[1]))
count = [0] * (N + 1)
ret = dict()

for py in PYsorted:
    p, y = py
    count[p] += 1
    ret[(p, y)] = count[p]

for py in PY:
    p, y = py
    print('%06d%06d' % (p, ret[(p, y)]))

Solution (Python):
N, M = list(map(int, input().split(' ')))
d = {}
ans = []



for i in range(M):
    p, y = list(map(int, input().split(' ')))
    if p not in d:
        d[p] = list()
    d[p].append(y)
    ans.append((p, y))
indexof = {}
for key in d:
    d[key] = sorted(d[key])
    indexof[key] = {}
    i = 1
    for v in d[key]:
        indexof[key][v] = i
        i += 1
for ken, t in ans:
    print('%s%s' % (str(ken).zfill(6), str(indexof[ken][t]).zfill(6)))

Solution (Python):
import os, sys, re, math

(N, M) = [int(i) for i in input().split()]
prefs = []
cities = []
for i in range(100000):
    prefs.append([])

for i in range(M):
    (p, y) = [int(j) for j in input().split()]
    city = [i, p, y, -1]
    prefs[p - 1].append(city)
    cities.append(city)

for pref in prefs:
    pref.sort(key=lambda x: x[2])
    for i in range(len(pref)):
        pref[i][3] = i

for c in cities:
    print ('%06d%06d' % (c[1], c[3] + 1))

Solution (Python):
_, nCities = map(int, input().split())
a = sorted([list(map(int, input().split())) + [i] for i in range(nCities)])
ret = [None] * nCities
prevPref = -1
order = 1
for pref, _ ,idx in a:
    if pref == prevPref:
        order += 1
    else:
        prevPref = pref
        order = 1
    ret[idx] = str(pref).zfill(6) + str(order).zfill(6)
print('\n'.join(ret))

Solution (Python):
N, M = map(int, input().split())

PY = []
for i in range(M):
    x = list(map(int, input().split()))
    x.append(i)
    PY.append(x)
    
PY = sorted(PY, key=lambda x: (x[0], x[1]))
num = PY[0][0]
ans = []
count = 1
for i in range(M):
    if PY[i][0] == num:
        tmp = [num, count, PY[i][2]]
        ans.append(tmp)
        count += 1
    else:
        num = PY[i][0]
        count = 1
        tmp = [num, count, PY[i][2]]
        ans.append(tmp)
        count += 1

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

for i in range(M):
    prefecture = str(ans[i][0])
    number = str(ans[i][1])
    print(prefecture.zfill(6) + number.zfill(6))

Solution (Python):
n, m = map(int, input().split())
pyi = [list(map(int, input().split())) + [i] for i in range(m)]
ids = [""] * m
s = {j + 1: 1 for j in range(n)}
for p, y, i in sorted(pyi, key=lambda d: d[1]):
    ids[i] = "%06d%06d" % (p, s[p])
    s[p] += 1
for iid in ids:
    print(iid)

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    py = []
    pyn = [1] * n
    for i in range(m):
        p, y = list(map(int, input().rstrip('\n').split()))
        py.append([p, y, i])
    py.sort()
    for i in range(len(py)):
        py[i][1] = pyn[py[i][0]-1]
        pyn[py[i][0] - 1] += 1
    py.sort(key=lambda x: x[2])
    for p, y, i in py:
        l = ["0"] * (6 - len(str(p)))
        l.append(str(p))
        l.append("0" * (6 - len(str(y))))
        l.append(str(y))
        print("".join(l))



if __name__ == '__main__':
    slove()

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(m):
  p,y=map(int,input().split())
  l.append([p,y,i])
l.sort()
y=[]
q=l[0][0]
r=0
for i in range(m):
  x=''
  if q==l[i][0]:
    r+=1
  else:
    r=1
    q=l[i][0]
  x+='0'*(6-len(str(l[i][0])))+str(l[i][0])
  x+='0'*(6-len(str(r)))+str(r)
  y.append([l[i][2],x])
y.sort()
for i in range(m):
  print(y[i][1])

Solution (Python):
import bisect

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

for i in range(m):
  p,q=map(int,input().split())
  l[p-1].append(q)
  d.append([p-1,q])
 
for i in range(n):
  if len(l[i])>0:
    l[i].sort()

for i in range(m):
  o = bisect.bisect_left(l[d[i][0]], d[i][1])+1
  print(str(d[i][0]+1).zfill(6)+str(o).zfill(6))

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(m):
    a,b=map(int,input().split())
    l.append([a,b])
x=sorted(l)
dic={}
x.append([0,0])
f=1
for i in range(m):
    if x[i][0]==x[i+1][0]:
        dic[str(x[i][0])+'000000'+str(x[i][1])]=f
        f+=1
    else:
        dic[str(x[i][0])+'000000'+str(x[i][1])]=f
        f=1
for i in range(m):
    b=dic[str(l[i][0])+'000000'+str(l[i][1])]
    p=len(list(str(l[i][0])))
    q=len(list(str(b)))
    ans=''
    for j in range(6-p):
        ans+='0'
    ans+=str(l[i][0])
    for j in range(6-q):
        ans+='0'
    ans+=str(b)
    print(ans)

Solution (Python):
N, M = map(int, input().split())
l = []
for i in range(M):
    P, Y = map(int, input().split())
    l.append([i, P, Y])
l = sorted(l, key = lambda x: (x[1], x[2]))
ans = []
prev_P = 0
for i in range(M):
    if prev_P != l[i][1]:
        j = 0
    j += 1
    ans.append([l[i][0], str(l[i][1]).zfill(6) + str(j).zfill(6)])
    prev_P = l[i][1]
ans = sorted(ans)
for i, s in ans:
    print(s)

Solution (Python):
n,m=map(int,input().split())
city_list = [[] for _ in range(n)]

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

for ppyy in py:
  city_list[ppyy[0]-1].append(ppyy[1])

dict = {}
for index, ppyy in enumerate(city_list):
  ppyy.sort()
  for index2, pppyyy in enumerate(ppyy):
    dict[pppyyy] = (str(index+1).zfill(6)+str(index2+1).zfill(6))

for ppyy in py:
  print(dict[ppyy[1]])

Solution (Python):
from sys import stdin
input = stdin.readline
n, m = map(int, input().split())

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

built = [1]*n
for i in range(m):
    ans[i][1] = built[ans[i][0]-1]
    built[ans[i][0]-1] += 1

for i in sorted(ans,key=lambda x:x[2]): print("%06d%06d" % (i[0],i[1]))

Solution (Python):
n,m=map(int,input().split())
a=[0]*m
for i in range(m):
  p,y=map(int,input().split())
  a[i]=[p,y,i]
a.sort()
p=a[0][0]
y=1
for i in range(m):
  if a[i][0]==p:
    a[i][1]=y
    y+=1
  else:
    p=a[i][0]
    y=1
    a[i][1]=y
    y+=1
a.sort(key=lambda x: x[2])
for i,j,k in a:
  print(str(i).zfill(6)+str(j).zfill(6))

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

ans = [[0,0,0] for i in range(m)]




pre = data[0][1]
num = 0
for i in range(m):
    ans[i][0] = data[i][1] 
    ans[i][2] = data[i][0] 
    if pre == data[i][1]:
        num += 1
    else:
        num = 1
    ans[i][1] = num
    pre = data[i][1]
ans = sorted(ans, key = lambda x:x[2])
for i in range(m):
    print("{:0=6}{:0=6}".format(ans[i][0],ans[i][1]))

Solution (Python):
n,m = map(int, input().split())
py = []
for i in range(m):
  a,b = map(int, input().split())
  py.append([a,b,i])
py.sort()
p = py[0][0]
y = 1
for i in range(m):
  if py[i][0] == p:
    py[i][1] = y
    y += 1
  else:
    py[i][1] = 1
    y = 2
    p = py[i][0]
py = sorted(py, key=lambda x:x[2])
for p,y,i in py:
  print("{:0=6}{:0=6}".format(p,y))

Solution (Python):
N,M=map(int,input().split())
py=[[i]+list(map(int,input().split())) for i in range(M)]
ken=[[] for _ in range(N)]

for i in py:
  ken[i[1]-1].append(i)
ans=[[i[1]] for i in py]
for i in ken:
  i.sort(key=lambda x:x[2])
  for j in range(len(i)):
    ans[i[j][0]].append(j+1)

for p,x in ans:
  print("".join([str(p).zfill(6),str(x).zfill(6)]))

Solution (Python):
from operator import itemgetter

N, M = map(int, input().split())
P = []
Y = []
IDX = []

for idx in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
    IDX.append(idx)
    
PYIDX = zip(P,Y,IDX)
PYIDX = sorted(PYIDX, key=itemgetter(1))
PYIDX = sorted(PYIDX, key=itemgetter(0))
PYIDX = [list(x) for x in PYIDX]

for i in range(M):
    if i == 0 or PYIDX[i-1][0] != PYIDX[i][0]:
        city_number = 1
    else:
        city_number += 1
    PYIDX[i].append(str(PYIDX[i][0]).zfill(6) + str(city_number).zfill(6))

PYIDX = sorted(PYIDX, key=itemgetter(2))

for idx in range(M):
    print(PYIDX[idx][3])

Solution (Python):

from bisect import bisect_left

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

t = [[] for _ in range(N)]
for P, Y in PY:
    t[P - 1].append(Y)

for i in range(N):
    t[i].sort()

for P, Y in PY:
    print("%06d%06d" % (P, bisect_left(t[P - 1], Y) + 1))