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):
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def main():
    N, M = map(int, readline().rstrip().split())
    inp = [list(map(int, readline().rstrip().split())) for _ in range(M)]
    pref = {}
    for p, y in inp:
        pref.setdefault(p, [])
        pref[p].append(y)

    pref_year_id = {}
    for p, years in pref.items():
        heapify(years)
        p_id = str(p).zfill(6)
        pref_year_id[p] = {}
        for i in range(1, len(years)+1):
            year = heappop((years))
            pref_year_id[p][year] = p_id + str(i).zfill(6)
    
    for p, y in inp:
        print(pref_year_id[p][y])

if __name__ == '__main__':
    main()

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

dic = {}
PY.sort(key = lambda x:x[1])
ken = [0 for i in range(N)]
for k,value,s in PY:
    ken[k-1] += 1
    s1 = str(k).zfill(6)
    s2 = str(ken[k-1])
    s2 = s2.zfill(6)
    dic[s] = s1+s2

ans = sorted(dic.items(),key=lambda x:x[0])

for i,j in ans:
    print(j)

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

dic = {}
PY.sort(key = lambda x:x[1])
ken = [0 for i in range(N)]
for k,value,s in PY:
    ken[k-1] += 1
    s1 = str(k).zfill(6)
    s2 = str(ken[k-1])
    s2 = s2.zfill(6)
    dic[s] = s1+s2

ans = sorted(dic.items(),key=lambda x:x[0])

for i,j in ans:
    print(j)

Solution (Python):
import itertools
import math
import fractions
import functools
n, m = map(int, input().split())
py = []
for i in range(m):
    l = list(map(int, input().split()))
    l.append(i)
    py.append(l)
 

 

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

ans = [0] * (m)
ans1 = [0] * (m)
memo = {}
for item in py:
    ken = item[0]
    year = item[1]
    idx = item[2]
    ith = memo.get(ken, 1)
    ans[idx] = ith
    ans1[idx] = ken
    memo[ken] = ith + 1

for i in range(m):
    print(str(ans1[i]).zfill(6) + str(ans[i]).zfill(6))

Solution (Python):
import itertools
import math
import fractions
import functools
n, m = map(int, input().split())
py = []
for i in range(m):
    l = list(map(int, input().split()))
    l.append(i)
    py.append(l)




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

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

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

    py[i].append(x)
    x += 1
py.sort(key=lambda x: x[2])

p_i = ""
x_i = ""
for i in range(m):
    if(len(str(py[i][0])) == 6):
        p_i = str(py[i][0])
    if(len(str(py[i][0])) == 5):
        p_i = '0' + str(py[i][0])
    if(len(str(py[i][0])) == 4):
        p_i = '00'+str(py[i][0])
    if(len(str(py[i][0])) == 3):
        p_i = '000' + str(py[i][0])
    if(len(str(py[i][0])) == 2):
        p_i = '0000'+str(py[i][0])
    if(len(str(py[i][0])) == 1):
        p_i = '00000' + str(py[i][0])
    if(len(str(py[i][3])) == 6):
        x_i = str(py[i][3])
    if(len(str(py[i][3])) == 5):
        x_i = '0' + str(py[i][3])
    if(len(str(py[i][3])) == 4):
        x_i = '00'+str(py[i][3])
    if(len(str(py[i][3])) == 3):
        x_i = '000' + str(py[i][3])
    if(len(str(py[i][3])) == 2):
        x_i = '0000'+str(py[i][3])
    if(len(str(py[i][3])) == 1):
        x_i = '00000' + str(py[i][3])

    print(p_i + x_i)

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

cities = {}
output = []
for i in range(M):
    x, y = map(int, input().split())
    cities[i+1] = [x,y]
    output.append(y)

ID = {}
county_old = 0
sorted_counties_years = sorted(cities.values())
for county,year in sorted_counties_years:
    if county_old == 0:
        county_old = county
        count = 1
        ID[year] = '{:06}{:06}'.format(county, count)
        count += 1
        continue
    elif county_old == county:
        ID[year] = '{:06}{:06}'.format(county, count)
        count += 1
    else:
        county_old = county
        count = 1
        ID[year] = '{:06}{:06}'.format(county, count)
        count += 1
for i in output:
    print(ID[i])

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

ypi=[[y,p,i] for i,(p,y) in enumerate(PY)]			
ypi.sort()

from collections import defaultdict

d=defaultdict(int)
ans=[0]*m

for y,p,i in ypi:
	d[p]+=1
	ans[i]=str(p).zfill(6)+str(d[p]).zfill(6)
	
print(*ans,sep="\n")

Solution (Python):
from bisect import bisect_right

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

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

A=[sorted(a) for a in A]												

for i in range(m):
	j=bisect_right(A[P[i]-1],Y[i])
	print(str(P[i]).zfill(6)+str(j).zfill(6))

Solution (Python):
def main():
    n, m = map(int, input().split(" "))
    p = []
    ids = [0 for _ in range(m)]
    y = []
    rev_y = dict()
    p_order = [1 for _ in range(n + 1)]
    for i in range(m):
        pi, yi = map(int, input().split(" "))
        p.append(pi)
        y.append(yi)
        rev_y[yi] = i
    y.sort()
    for year in y:
        city_index = rev_y[year]
        prefecture_id = p[city_index]
        born_time = p_order[prefecture_id]
        ids[city_index] = born_time
        p_order[prefecture_id] += 1
    for i in range(m):
        print("%s%s" % (padding_str(p[i]), padding_str(ids[i])))


def padding_str(n):
    return str(n).zfill(6)


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
from collections import defaultdict
d=defaultdict(list)
py=[]
for i in range(m):
    p,y=map(int,input().split())
    d[p].append(y)
    py.append((p,y))

for k in d.keys():
    d[k]=sorted(d[k])

from bisect import bisect_right
for i in range(m):
    p=py[i][0]
    y=py[i][1]
    x=bisect_right(d[p], y)
    print('0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(x)))+str(x))

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

d = [[] for _ in range(n)]
P = [0] * m
Y = [0] * m

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

for i in range(m):
    p,y = P[i],Y[i]
    D = d[p - 1]
    idx = bisect.bisect_left(D, y) + 1
    print(str(p).zfill(6) + str(idx).zfill(6))

Solution (Python):
n,m=map(int,input().split())
lis=[]
for i in range(0,m):
  p,q=map(int,input().split())
  lis.append([q,p,i])
lis.sort()
ken=[1]*n
res=[]
for i in range(0,m):
  attack=lis[i]
  kenken=attack[1]
  ken_count=ken[kenken-1]
  moji=""
  moji+="0"*(6-len(str(kenken)))+str(kenken)+"0"*(6-len(str(ken_count)))+str(ken_count)
  ken[kenken-1]+=1
  res.append([attack[2],moji])
  
res.sort()
for i in range(0,m):
  print(res[i][1])

Solution (Python):

import sys
from itertools import *
from operator import itemgetter


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    items = [(P[i], Y[i]) for i in range(M)]

    key_to_value_to_rank = {}
    for key, sorted_items in groupby(sorted(items), key = itemgetter(0)):
        value_to_rank = dict((item, index + 1) for index, item in enumerate(map(lambda x: x[1], sorted_items)))
        key_to_value_to_rank[key] = value_to_rank

    for key, value in items:
        rank = key_to_value_to_rank[key][value]
        print('{0:06d}'.format(key, rank) + '{0:06d}'.format(rank))

    return



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):

import sys
from itertools import *
from operator import itemgetter


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    items = [(P[i], Y[i]) for i in range(M)]

    key_to_value_to_rank = {}
    for key, sorted_items in groupby(sorted(items), key = itemgetter(0)):
        value_to_rank = dict((item, index + 1) for index, item in enumerate(map(lambda x: x[1], sorted_items)))
        key_to_value_to_rank[key] = value_to_rank

    for key, value in items:
        rank = key_to_value_to_rank[key][value]
        print('{0:06d}'.format(key, rank) + '{0:06d}'.format(rank))

    return



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):

import sys

dic = {}

def list_sort(x):
    values = dic[x]
    values.sort()

    return {x: values}

def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    for i in range(N):
        dic[i + 1] = []
    
    for i in range(M):
        dic[P[i]].append(Y[i])

    sorted_dic = {}
    for key in dic.keys():
        tmp = {}
        values = dic[key]

        values.sort()
        for i in range(len(values)):
            tmp[values[i]] = i + 1

        sorted_dic[key] = tmp


    for m in range(M):
        key = P[m]
        value = Y[m]
        sorted_ranked_dic = sorted_dic[key]
        rank = sorted_ranked_dic[value]

        print('{0:06d}'.format(key, rank) + '{0:06d}'.format(rank))



    return



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())
ppyy = [list(map(int, input().split())) for _ in range(m)]
order = [{}] * (n + 1)
cnt = [1] * (n + 1)
for p, y in sorted(ppyy, key=lambda x: x[1]):
    order[p].update({y: cnt[p]})
    cnt[p] += 1
for p, y in ppyy:
    cnt[p] += 1
    print(str(format(p, '06')) + str(format(order[p][y], '06')))

Solution (Python):
n, m = [int(x) for x in input().split()]

temp_list = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = [int(x) for x in input().split()]
    temp_list[p].append((y, i))

ans_list = [""] * m
for p in range(1, n + 1):
    temp_list[p].sort()
    for j in range(len(temp_list[p])):
        _, i = temp_list[p][j]
        ans_list[i] = "{:06}{:06}".format(p, j + 1)

for ans in ans_list:
    print(ans)

Solution (Python):

import sys
from bisect import bisect_right

def main():
    N, M = map(int, input().split())
    P = [None] * M
    Y = [None] * M
    ans = [set() for _ in range(N)]
    for i in range(M):
        p, y = map(int, input().split())
        P[i], Y[i] = p, y
        ans[p-1].add(y)
    ans = [sorted(a) for a in ans]
    
    for i in range(M):
        k = P[i]
        j = bisect_right(ans[k-1],Y[i])
        print(str(k).zfill(6)[-6:] + str(j).zfill(6)[-6:])


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
PYI = []
for i in range(M):
    p, y = map(int, input().split())
    PYI.append([p, y, i])
PYI.sort(key=lambda x: (x[0], x[1]))


P = 0
c = 1
ans = []
for p, y, i in PYI:
    if p != P:
        c = 1
        P = p
    else:
        c += 1
    ans.append([i, '{:06d}{:06d}'.format(p, c)])

ans.sort(key=lambda x: x[0])
for i, a in ans:
    print(a)

Solution (Python):
n, m = map(int, input().split())
ipyth = [[i] * 4 for i in range(m)]
for i in range(m):
    ipyth[i][1], ipyth[i][2] = map(int, input().split())
ipyth.sort(key=lambda x:(x[1], x[2]))
for i in range(m):
    if i:
        if ipyth[i][1] == ipyth[i - 1][1]:
            ipyth[i][3] = ipyth[i - 1][3] + 1
        else:
            ipyth[i][3] = 1
    else:
        ipyth[i][3] = 1
ipyth.sort(key = lambda x: x[0])
for i in range(m):
    print(str(ipyth[i][1]).zfill(6) + str(ipyth[i][3]).zfill(6))

Solution (Python):
from collections import defaultdict

N, M = map(int,input().split())
l = [tuple(map(int,input().split())) for i in range(M)]


l_sorted = sorted((y,p,i) for i,(p,y) in enumerate(l))

d = defaultdict(lambda: 0)

ans = [None] * M

for a,b,c in l_sorted:
    d[b] += 1
    ans[c] = str(b).zfill(6) + str(d[b]).zfill(6)
print(*ans, sep='\n')

Solution (Python):
n,m = map(int,input().split())
t = []
for i in range(m):
    p, y = map(int,input().split())
    t.append([i,p,y,0])
t.sort(key=lambda x:x[2])                 
t.sort(key=lambda x:x[1])                 
city = t[0][1]
city_num = 0
for i in range(m):                       
    if t[i][1] == city:
        city_num += 1
        t[i][3] += city_num
    else:
        city = t[i][1]
        t[i][3] = 1
        city_num = 1
t.sort()                                 
for i in t:
    ans = "%06d" % i[1] + "%06d" % i[3]
    print(ans)

Solution (Python):
n, m = map(int,input().split())
li = []
ans = []


for i in range(m):
    x = list(map(int,input().split()))
    x.append(i)
    li.append(x)

li.sort()

for i in range(len(li)):
    if i == 0:
        y = 1
    elif li[i][0] == li[i-1][0]:
        y += 1
    else:
        y = 1
    li[i].append(str(li[i][0]).rjust(6,'0') + str(y).rjust(6,'0'))

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

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

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

for i in range(M):
    pi, yi = map(int, input().split())
    records.append([i, pi, yi, "X"])

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



city = records[0][1]
city_num = 0

for i in range(M):
    if records[i][1] == city:
        city_num += 1
        records[i][3] = city_num
    else:
        city = records[i][1]
        records[i][3] = 1
        city_num = 1
records.sort()
for record in records:
    ans = "%06d" % record[1] + "%06d" % record[3]
    print(ans)

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(m)]
ypi = sorted((y, p, i) for i, (p, y) in enumerate(PY))
d = defaultdict(lambda: 0)

ans = [None]*m

for y, p, i in ypi:
    d[p] += 1
    ans[i] = str(p).zfill(6) + str(d[p]).zfill(6)

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

Solution (Python):
n, m = map(int,input().split())
ypi = []
for i in range(m):
    p, y = map(int,input().split())
    p = str(p)
    p = '0'*(6-len(p)) + p
    ypi.append((y, p, i))
ypi.sort()

p_dict = {}
for y, p, i in ypi:
    p_dict[p] = []

for y, p, i in ypi:
    p_dict[p].append(i)

ans_l = [0]*m
for p, i_l in p_dict.items():
    for j, i in enumerate(i_l):
        j = str(j+1)
        j = '0'*(6-len(j)) + j
        ans_l[i] = p + j

for val in ans_l:
    print(val)

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

py=[]


p2year = [[] for _ in range(n+1)]

for _ in range(m):
    p,y=map(int,input().split())
    py.append((p,y))
    p2year[p].append(y)


from collections import defaultdict
py2index = defaultdict(lambda: 0) 

for item in range(n+1):
    p2year[item].sort()
    for index,temp in enumerate(p2year[item]):
        py2index[(item,temp)]=index+1

for item in py:
    pp=item[0]
    yy=item[1]
    result=str(pp).zfill(6)+str((py2index[(pp,yy)])).zfill(6)
    print(result)

Solution (Python):
N,M = map(int,input().split()) 
Pref_info = [[] for _ in range(N)] 
for i in range(M):
    P,Y = map(int,input().split())
    Pref_info[P - 1].append([Y,i])
ans = [""]* M 
for i in range(N): 
    Pref_info[i].sort()
    for index, p in enumerate(Pref_info[i]):
        ans[p[1]] = "{0}{1}".format(str(i+1).zfill(6),str(index+1).zfill(6))
for i in ans:
    print(i)

Solution (Python):
N,M = map(int, input().split())  
piys = [[] for _ in range(N)]   
for i in range(M):  
    p, y = map(int, input().split())  
    piys[p-1].append((y,i))  

ans = [None]*M  
for p,iys in enumerate(piys):  
    iys.sort()  
    for k,(y,i) in enumerate(iys):  
        ans[i] = "%06d%06d" % (p+1,k+1)  

for i in ans:  
    print(i)

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


ypi = sorted((y,p,i) for i,(p,y) in enumerate(PY))
 
from collections import defaultdict
d = defaultdict(lambda: 0)


ans = [None] * M

for y,p,i in ypi:
    d[p] += 1

    
    
    ans[i] = str(p).zfill(6) + str(d[p]).zfill(6)
print(*ans, sep='\n')

Solution (Python):
import bisect
N,M=map(int, input().split())
P=[[] for _ in range(N)]
L=[]
for i in range(M):
    p,y=map(int, input().split())
    L.append((p,y))
    P[p-1].append(y)

newP=[]
for p in P:
    p=sorted(p)
    newP.append(p)

for i in range(M):
    t=L[i]
    p,y=t
    num=bisect.bisect_right(newP[p-1],y)
    
    p=str(p).zfill(6)
    num=str(num).zfill(6)
    print(p+num)

Solution (Python):
def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())

    prefectures = [[] for _ in range(N + 1)]
    for m in range(M):
        p, y = map(int, input().split())
        prefectures[p].append((y, m))

    ans = [''] * M
    for p, pref in enumerate(prefectures, start=0):
        pref.sort(key=itemgetter(0))
        for i, (_, m) in enumerate(pref, start=1):
            ans[m] = '{:06d}{:06d}'.format(p, i)

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


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    cities = sorted(
        (Yi, Pi, i)
        for i, (Pi, Yi) in enumerate(zip(P, Y))
    )
    ans = [""] * M
    cnt = defaultdict(int)
    for Yi, Pi, i in cities:
        cnt[Pi] += 1
        ans[i] = "%06d%06d" % (Pi, cnt[Pi])

    for ansi in ans:
        print(ansi)


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):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush



def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

def main():
    mod = 10**9+7
    

    
    N, M = map(int, input().split())
    
    
    
    tot=[[] for _ in range(N+1)]
    ys=[0]*M
    for i in range(N):
        heapify(tot[i])
    for i in range(M):
        P, Y = map(int, input().split())
        heappush(tot[P],[Y,i])
        ys[i]=Y
    tset=[]
    ans=['']*M
    for i in range(N+1):
        t1=tot[i]
        if len(t1)<1:continue
        p=str(i).zfill(6)
        j=0
        while len(t1):
            t, i1=heappop(t1)
            tx=str(j+1).zfill(6)
            ans[i1]=''.join((p,tx))
            j+=1
    print('\n'.join(ans))





if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush



def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

def main():
    mod = 10**9+7
    

    
    N, M = map(int, input().split())
    
    
    
    tot=[[] for _ in range(N+1)]
    ys=[0]*M
    for i in range(N):
        heapify(tot[i])
    for i in range(M):
        P, Y = map(int, input().split())
        heappush(tot[P],[Y,i])
        ys[i]=Y
    tset=[]
    ans=['']*M
    for i in range(N+1):
        t1=tot[i]
        if len(t1)<1:continue
        p=str(i).zfill(6)
        j=0
        while len(t1):
            t, i1=heappop(t1)
            tx=str(j+1).zfill(6)
            ans[i1]=p+tx
            j+=1
    print('\n'.join(ans))





if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush



def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

def main():
    mod = 10**9+7
    

    
    N, M = map(int, input().split())
    
    
    
    tot=[[] for _ in range(N+1)]
    ys=[0]*M
    for i in range(N):
        heapify(tot[i])
    for i in range(M):
        P, Y = map(int, input().split())
        heappush(tot[P],[Y,i])
        ys[i]=Y
    tset=[]
    ans=['']*M
    for i in range(N+1):
        t1=tot[i]
        if len(t1)<1:continue
        p=str(i).zfill(6)
        j=0
        while len(t1):
            t, i1=heappop(t1)
            tx=str(j+1).zfill(6)
            ans[i1]=p+tx
            j+=1
    print('\n'.join(ans))





if __name__ == "__main__":
    main()

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

import heapq
N,M = (int(x) for x in input().split())
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    if p:
        heapq.heapify(p)
        while p:
            temp = heapq.heappop(p)
            ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
            count += 1
print('\n'.join(ans))

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

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

ans = [''] * m
for p in range(10 ** 5):
    prefecture = prefectures[p]
    prefecture.sort(key=lambda x: x[0])
    for i in range(len(prefecture)):
        ans[prefecture[i][1]] = '{:006}{:006}'.format(p + 1, i + 1)

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

Solution (Python):
n,m=map(int,input().split())
py=[]
ans=[0]*m
for j in range(m):
    py.append(list(map(int,input().split()))+[j])
py.sort(key=lambda x:x[1])
p=[0]*n
for i in range(m):
  p[py[i][0]-1]+=1
  ans[py[i][2]]='0'*(6-len(str(py[i][0])))+str(py[i][0])+'0'*(6-len(str(p[py[i][0]-1])))+str(p[py[i][0]-1])
for k in range(m):
    print(ans[k])

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
PY = defaultdict(dict)
for i in range(M):
    temp = list(map(int, input().split()))
    PY[temp[0]][temp[1]] = i
PY_sort = sorted(PY.items(), key=lambda x: x[0])

city = {}
for n, ms in PY_sort:
    ms_sort = sorted(ms.items(), key=lambda x: x[0])
    k = 1
    for m, i in ms_sort:
        city[i] = "".join([str(n).zfill(6), str(k).zfill(6)])
        k += 1
city_sort = sorted(city.items(), key=lambda x: x[0])
for i in range(M):
    print(city_sort[i][1])

Solution (Python):
N, M = map(int,input().split())
C = [[] for k in range(N)]
for k in range(M):
    P, Y = map(int,input().split())
    C[P-1].append([Y,k])
D = []
for e in C:
    D.append(sorted(e))
A = [0]*M
for k in range(N):
    c = 1
    for e in D[k]:
        A[e[1]] = (k+1)*1000000 + c
        c += 1
for e in A:
    print(str(e).zfill(12))

Solution (Python):
import bisect
from collections import defaultdict
n,m = map(int,input().split())
p = [list(map(int, input().split())) for _ in range(m)]
 
a = defaultdict(list)
for x,y in sorted(p):
    a[x].append(y)
for x,y in p:
    
    z=bisect.bisect(a[x],y)
    print("{0:06d}{1:06d}".format(x,z))

Solution (Python):
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))

Solution (Python):
N, M = map(int, input().split())
PY = [tuple(list(map(int, input().split()))+[i]) for i in range(M)]
PY.sort(key=lambda x: x[1])
ans = ['']*M
P = [0]*N
for p, y, i in PY:
    ret = ''
    p -= 1
    P[p] += 1
    ret += '{:0=6}'.format(p+1)
    ret += '{:0=6}'.format(P[p])
    ans[i] = ret
print(*ans, sep='\n')

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from bisect import bisect_left

n, m = map(int, readline().split())
py = [list(map(int, readline().split())) for _ in range(m)]
check = sorted(py)
idx = [0] * (n + 1)
memo = 0
for i, (p, _) in enumerate(check):
    if memo != p:
        idx[p] = i
        memo = p
for p, y in py:
    yy = str(bisect_left(check, [p, y]) - idx[p] + 1)
    p = str(p)
    print('0' * (6 - len(p)) + p + '0' * (6 - len(yy)) + yy)

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

pnow = pyi[0][0]
cnt = 1

ans = [-1 for _ in range(m)]

for p,y,i in pyi:
  if pnow != p:
    cnt = 1
    pnow = p
  ans[i] = str(p).zfill(6) + str(cnt).zfill(6)
  cnt += 1
print("\n".join(ans))

Solution (Python):
import bisect

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

data = [[] for _ in range(n)]
query = []

for i in range(m):
    array = list(map(int, input().split()))
    query.append(array)
    a = array[0] - 1
    b = array[1]
    data[a].append(b)

cnt = 0
for i in data:
    i.sort()
    data[cnt] = i
    cnt += 1
    
for i, j in query:
    num = bisect.bisect_left(data[i-1], j) + 1
    x = str(i).zfill(6)
    y = str(num).zfill(6)
    z = str(x) + str(y)
    print(z)

Solution (Python):
from bisect import bisect_left
N,M = map(int,input().split())
C = {i:[] for i in range(1,N+1)}
city = [0 for _ in range(M+1)]
for j in range(1,M+1):
    p,y = map(int,input().split())
    C[p].append((y,j))
    city[j]=(p,y)
for p in C:
    if len(C[p])>0:
        C[p] = sorted(C[p],key=lambda x:x[0])
for j in range(1,M+1):
    p,y = city[j]
    ind = bisect_left(C[p],(y,j))
    p = str(p)
    if len(p)<6:
        p ="0"*(6-len(p))+p
    x = str(ind+1)
    if len(x)<6:
        x = "0"*(6-len(x))+x
    print(p+x)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  


N, M = read_ints()
cnts = [0] * N
YPI = []
for i in range(M):
    p, y = read_ints()
    YPI.append((y, p - 1, i))

YPI.sort()  
IDs = []
for y, p, i in YPI:
    cnts[p] += 1
    x = str(cnts[p])
    p = str(p + 1)

    IDs.append((i, p.zfill(6) + x.zfill(6)))

IDs.sort()
for i, iid in IDs:
    print(iid)

Solution (Python):
from collections import defaultdict

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

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

ans = [''] * M
for p, grp in A.items():
    for j, (_, i) in enumerate(sorted(grp), start=1):
        ans[i] = '%06d%06d' % (p, j)
print(*ans, sep='\n')

Solution (Python):
import bisect
n, m = map(int, input().split())
Ps = [[]for _ in range(n)]
PY = []
for _ in range(m):
    p, y = map(int, input().split())
    Ps[p-1].append(y)
    PY.append((p, y))

for ls in Ps:
    ls.sort()

for p, y in PY:
    pid = "{:06}".format(p)
    cid = "{:06}".format(bisect.bisect_right(Ps[p-1], y))
    print(pid+cid)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    PY = []
    for i in range(m):
        p, y = map(int, input().split())
        PY.append([i, p, y])
    PY = sorted(PY, key=lambda x: x[2])
    PY = sorted(PY, key=lambda x: x[1])

    res = [] * m
    prev = PY[0][1]
    last = 0
    for i in range(m):
        idx, p, y = PY[i]
        if prev != p:
            last = 1
            prev = p
        else:
            last += 1

        id = str(p).zfill(6) + str(last).zfill(6)
        res.append([idx, id])

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


if __name__ == '__main__':
    resolve()