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
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
l=[None]*M
for i in range(M):
    P,Y=map(int,input().split())
    l[i]=(P,Y,i)
l.sort()
a=[None]*M
s=0
t=1
for i in l:
    if i[0]==s:
        t+=1
    else:
        t=1
        s=i[0]
    a[i[2]]="{:06d}".format(i[0]) + "{:06d}".format(t)
print(*a,sep="\n")

Solution (Python):
n,m=map(int,input().split())
li=[]
city_counter = [1] * (10**5+2)
ans=[]

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

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

for i in range(m):
    tmp = str(li[i][0]).zfill(6) + str(city_counter[li[i][0]]).zfill(6)
    ans.append((tmp,li[i][2]))
    city_counter[li[i][0]] += 1

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

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

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

from collections import defaultdict
d = defaultdict(list)
for tmp in l:
    d[tmp[0]].append(tmp[1])
for key in d:
    lis = d[key]
    lis.sort()
    d[key] = lis

import bisect
for tmp in l:
    p = tmp[0]
    y = tmp[1]

    lut = d[p]
    ind = bisect.bisect_left(lut,y)+1
    print(str(p).zfill(6)+str(ind).zfill(6))

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

sorted_P_Y = sorted(P_Y)
rank = 1
prev_p = -1
for p, y, i in sorted_P_Y:
    if prev_p != p:
        rank = 1
    else:
        rank += 1
    P_Y[i].append(rank)
    prev_p = p
for p, _, _, rank in P_Y:
    print(str(p).rjust(6, '0') + str(rank).rjust(6, '0'))

Solution (Python):
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    PY = [list(map(int,input().split())) + [index] for index  in range(M)]
    PY.sort(key = itemgetter(1))
    PY.sort(key = itemgetter(0))
    Ans = [""]*M
    Ken = [0]*(N + 1)
    for i  in range(M):
        p,y,index = PY[i]
        Ken[p] += 1
        Ans[index] = str(p).zfill(6) + str(Ken[p]).zfill(6)
    print(*Ans,sep="\n")
    return 

if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
dic=[]
ans=[]
number=[1] * (10**5+2)

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

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

for i in range(m):
    tmp=str(dic[i][0]).zfill(6)+str(number[dic[i][0]]).zfill(6)
    number[dic[i][0]]+=1
    ans.append((tmp,dic[i][2]))

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

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

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

cities = list()
for i in range(m):
    pi, pm = [int(x) for x in input().split(' ')]
    cities.append([pi, pm, i])

p = [0] * (n+1)
for c in sorted(cities, key=lambda city: city[1]): 
    p[c[0]] += 1 
    c.append(p[c[0]])

for c in cities:
    print('{:06d}{:06d}'.format(c[0], c[3]))

Solution (Python):
n,m = map(int,input().split())
py = []
li = [1] * (10**5 + 10)

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

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

ans = []

for p,y,i in py:
    ans_tmp = '0' * (6 - len(str(p))) + str(p) + '0' * (6 - len(str(li[p]))) + str(li[p])
    li[p] += 1
    ans.append([ans_tmp, i])

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

Solution (Python):
N,M = map(int,input().split())
p,y = 0,0
my_dict = dict()
def genFrstSix(P):
	str_ = str(P)
	while(len(str(str_))<6):
		str_ = "0"+ str_
		
	return str_
tup,P,Y= [],[],[]
for i in range(M):
	p,y = map(int,input().split())
	tup.append((p,y))
	if p in my_dict.keys():
		my_dict[p].append(y)
	else:
		my_dict[p] = [y]


for key in my_dict.keys():
	sorted_y = sorted(my_dict[key])
	ys = {y:i+1 for i,y in enumerate(sorted_y)}
	
	my_dict[key] = ys	
	
		

for each in tup:
	
	
	p = each[0]
	y = each[1]
	print('{:06}{:06}'.format(p,my_dict[p][y]))

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

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

L = [[] for i in range(N)]
D = []

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

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

for i in range(M):
    ans = str(D[i][0]).zfill(6)+ str(bisect.bisect_left(L[D[i][0]-1], D[i][1])+1).zfill(6)
    print(ans)

Solution (Python):
import bisect
from collections import defaultdict
d = defaultdict(list)

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

for i in li:
  d[i[0]].append(i[1])
  
for s in d:
  d[s].sort()
  
for i in li:
  index = bisect.bisect_left(d[i[0]],i[1])
  print(str(i[0]).zfill(6) + str(index+1).zfill(6))

Solution (Python):

import re
import math
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="number"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s

def keta(n):
    n=str(n)
    for a in range(6-len(n)):
        n="0"+n
    return n
n,m=map(int,input().split())
P=[[] for a in range(n)]
for a in range(m):
    p,y=map(int,input().split())
    p-=1
    city=a
    P[p].append({"y":y,"city":city})
C=[]
for a in range(n):
    P[a].sort(key=lambda x:x["y"])
    for b in range(len(P[a])):
        C.append([keta(a+1)+keta(b+1),P[a][b]["city"]])
C.sort(key=lambda x:x[1])
for a in C:
    print(a[0])

Solution (Python):
N,M=map(int,input().split())
P=[]
for i in range(M):
  P.append(list(map(int,input().split())))
  P[i].append(i)
S_P = sorted(
  P,
  key = lambda x: (x[0], x[1])
)
T=0
BT=S_P[0][0]
ANS=[]
for p in S_P:
  if BT != p[0]:
    BT=p[0]
    T=1
  else:
    T+=1
  ANS.append([p[2], '{:0=6}{:0=6}'.format(BT,T)])
  
A = sorted(
  ANS,
  key = lambda x: x[0]
)
for ans in A:
  print(ans[1])

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

x = 1
a = 1
ans = []
for i, p, y in py:
    if x != int(p):
        x = int(p)
        a = 1
    
    ans.append([i, p.zfill(6)+str(a).zfill(6)])
    a += 1

for i, v in sorted(ans):
    print(v)

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

x = 1
a = 1
ans = []
for i, p, y in py:
    if x != int(p):
        x = int(p)
        a = 1
    
    ans.append([i, p.zfill(6)+str(a).zfill(6)])
    a += 1

for i, v in sorted(ans):
    print(v)

Solution (Python):
from collections import defaultdict

def solve(n, m, PY):
    index = {
        y: i
        for i, (_, y) in enumerate(PY)
    }

    PY.sort(key=lambda py: py[1])
    counts = defaultdict(int)
    ret = [''] * m
    for p, y in PY:
        counts[p] += 1
        ret[index[y]] = '{0:06d}{1:06d}'.format(p, counts[p])
    return ret

_n, _m = map(int, input().split())
_PY = [list(map(int, input().split())) for _ in range(_m)]
print(*solve(_n, _m, _PY), sep='\n')

Solution (Python):
import sys
import collections
import bisect as bs
input=sys.stdin.readline
n,m=map(int,input().split())
d=collections.defaultdict(list)
L=[]
for i in range(m):
    a,b=map(int,input().split())
    L.append((a,b))
for x,y in sorted(L):
    d[x].append(y)
for x,y in L:
    z=bs.bisect(d[x],y)
    print("%06d%06d"%(x,z))

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)




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

PREFECTURE = defaultdict(list)
for p, y in PY:
    PREFECTURE[p].append(y)

for i in PREFECTURE.keys():
    ys = sorted(PREFECTURE[i])
    y_to_i = {y: i+1 for i, y in enumerate(ys)}
    PREFECTURE[i] = y_to_i

for p, y in PY:
    print('{:06}{:06}'.format(p, PREFECTURE[p][y]))

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

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

PY.sort()

ans=[None]*M

p=0
x=0
for i in range(M):
    if PY[i][0]!=p:
        p=PY[i][0]
        x=1
    else:
        x+=1
    pp=str(p)
    np=len(pp)
    xx=str(x)
    nx=len(xx)
    ans[PY[i][2]]="0"*(6-np)+pp+"0"*(6-nx)+xx
    
for i in range(M):
    print(ans[i])

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

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

PY.sort()

ans=[None]*M

p=0
x=0
for i in range(M):
    if PY[i][0]!=p:
        p=PY[i][0]
        x=1
    else:
        x+=1
    pp=str(p)
    np=len(pp)
    xx=str(x)
    nx=len(xx)
    ans[PY[i][2]]="0"*(6-np)+pp+"0"*(6-nx)+xx
    
for i in range(M):
    print(ans[i])

Solution (Python):

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

py.sort(key=lambda na:(na[1],na[2]))

count=0
m_city=py[0][1]
for i in range(m):
    si=py[i][1]
    if m_city==si:
        count+=1
        py[i].append(count)
    else:
        count=1
        m_city=py[i][1]
        py[i].append(count)
    
py.sort(key=lambda na:na[0])


for i in range(m):
    print('{:0>6}'.format(py[i][1]),end="")
    print('{:0>6}'.format(py[i][3]))

Solution (Python):
N, M = map(int, input().split())
l = []
cnt = [0 for i in range(N+1)]
k_id = [0 for i in range(M)]
for i in range(M):
    P, Y = map(int, input().split())
    l.append([Y, P , i])
l.sort(key=lambda x: x[0])
for i in range(M):
    y, p, idx = l[i][0], l[i][1], l[i][2]
    cnt[p] += 1
    k_id[idx] = [p, cnt[p]]
for i in range(M):
    print(str(k_id[i][0]).zfill(6)+str(k_id[i][1]).zfill(6))

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

for i in range(m):
    p, y = map(int, input().split())
    py[i][0] = i
    py[i][1] = p
    py[i][2] = y

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

now_pre = py[0][1]
now_idx = 0
for i in py:
    num_p = str(i[1]).zfill(6)
    if i[1] == now_pre:
        now_idx += 1
    else:
        now_idx = 1
        now_pre = i[1]
    num_y = str(now_idx).zfill(6)
    i[3] = num_p + num_y

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

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

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

Solution (Python):

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

D=[]

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



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


for i in range(M):
    ans=str(D[i][0]).zfill(6)+str(bisect.bisect_left(L[D[i][0]-1],D[i][1])+1).zfill(6)
    print(ans)

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

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

prefec = 0
cnt = 1
for py in PY:
    if py[0] != prefec:
        prefec = py[0]
        cnt = 1
    py.append(cnt)
    cnt += 1

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

for py in PY:
    print('{0:06d}{1:06d}'.format(py[0], py[3]))

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

ans=[[] for i in range(m)]
p_list=[[] for i in range(n+1)]

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

 ans[i]=str(p).zfill(6)

 p_list[p].append([i,y])

for pp in p_list:
 pp=sorted(pp,key=lambda x:x[1])
 num=0
 for ppp in pp:
  num+=1
  ans[ppp[0]]+=str(num).zfill(6)
 num=0

for i in ans:
 print(i)

Solution (Python):
N,M = map(int,input().split())
PYi = []
pmin = float('inf')
for i in range(M):
    p,y = map(int,input().split())
    PYi.append([p,y,i])
    pmin = min(pmin,p)
PYi.sort()
now = pmin
count = 1
for i in range(M):
    p,y,j = PYi[i]
    if now == p:
        PYi[i][1] = count
        count += 1
    else:
        now = p
        PYi[i][1] = 1
        count = 2
PYi.sort(key = lambda x:x[2])
for p,y,i in PYi:
    p = str(p)
    y = str(y)
    print('0'*(6-len(p)) + p + '0'*(6-len(y)) + y)

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

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


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

input_list = []

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


for j in range(n):
    block[j] = sorted(list(set(block[j])))

for i in range(m):
    p, y = input_list[i]
    est_num = bisect.bisect_left(block[p], y)
    print(str(p+1).zfill(6), str(est_num+1).zfill(6), sep='')

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

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

    dp = [[] for _ in range(n)]
    ans = [0] * m

    for i in range(m):
        p, y = map(int, input().split())
        dp[p - 1].append((y, i))
    
    for j, k in enumerate(dp):
        k.sort()    
        for l, (s, t) in enumerate(k):
            ans[t] = str(j + 1).zfill(6) + str(l + 1).zfill(6)
    
    print(*ans, sep = "\n")


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

prep=PYi[0][0]
cc=1
PYi[0][1]=cc
for j in range(1,M):
    p=PYi[j][0]
    if prep==p:
        cc+=1
    else:
        cc=1
    PYi[j][1]=cc
    prep=p
        
PYi.sort(key=lambda x:x[2])

def padding(A):
    A=str(A)
    while len(A)<6:
        A=str(0)+A
    return A

for i in range(M):
    ansi=padding(PYi[i][0])+padding(PYi[i][1])
    print(ansi)

Solution (Python):
def main():
    N, M = map(int, input().split(" "))
    formed_year = []
    order = [0] * (N + 1)
    cities_order = [0] * (M + 1)
    for i in range(1, M + 1):
        p, y = map(int, input().split(" "))
        formed_year.append((i, p, y))
    formed_year_formated = sorted(formed_year, key=lambda x: x[2])
    for year in formed_year_formated:
        order[year[1]] += 1
        cities_order[year[0]] = order[year[1]]
    for i in range(M):
        print(str(formed_year[i][1]).zfill(6) + str(cities_order[formed_year[i][0]]).zfill(6))


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
XY_list = [[] for i in range(N)]
ans_list = [None] * M
for i in range(M):
  X, Y = map(int, input().split())
  XY_list[X - 1].append((Y, i))
for j, k in enumerate(XY_list):
  k.sort()
  for l, (y, m) in enumerate(k):
    ans_list[m] = str(j + 1).zfill(6) + str(l + 1).zfill(6)
print(*ans_list, sep = "\n")

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

dic_PY = defaultdict(list)
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]
for p, y in sorted(PY):
  dic_PY[p] += [y]
  
for p, y in PY:
  z = bisect_right(dic_PY[p], y)
  print("%06d%06d"%(p,z))

Solution (Python):
N, M = map(int, input().split())
D = [[] for _ in range(N)]
for i in range(M):
    P, Y = map(int, input().split())
    D[P - 1].append((Y, i))
ans = [None] * M
for i, d in enumerate(D):
    d.sort()
    for k, (Y, j) in enumerate(d):
        ans[j] = "%06d%06d" % (i + 1, k + 1)
print(*ans, sep='\n')

Solution (Python):
import sys


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

C = [None] * M
for i, x in enumerate(sys.stdin.readlines()):
    P, Y = map(int, x.split())
    C[i] = (P, Y, i)

C.sort()

Num = [None] * M

pp = 0
cnt = 0
for P, Y, i in C:
    if P != pp:
        cnt = 1
    else:
        cnt += 1
    pp = P
    Num[i] = (P, cnt)

for P, cnt in Num:
    P = str(P).zfill(6)
    cnt = str(cnt).zfill(6)
    print(P + cnt)

Solution (Python):

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

PY_dict = dict() 
PY_list = list() 
PY_ans = dict()  


for i in range(M):
    P,Y = map(int, input().split())
    
    PY_list.append((str(P).zfill(6),Y))
    
    if P not in PY_dict:
        PY_dict[P] = list()
        
    PY_dict[P].append(Y)
        

for PY in PY_dict.items():
    P = str(PY[0]).zfill(6)
    Y = PY[1]
    Y.sort(reverse=False)
        
    for i in range(1,len(Y)+1):
        number = P + str(i).zfill(6)
        PY_ans[(P,Y[i-1])] = number
        

for PY in PY_list:
    print(PY_ans[PY])

Solution (Python):

import sys
import math
import os
import itertools
import _collections
import string

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]

class Util():
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)

def main():
    N,M = cin.mapInt()
    P = []
    for i in range(M):
        p,y = cin.mapInt()
        P.append([p,y,i,""])
    P.sort(key=lambda x:(x[1],x[0],x[2]))
    pref = [1] * (N + 1)
    for i in range(M):
        a = pref[P[i][0]]
        pref[P[i][0]] = a + 1
        id = str(P[i][0]).zfill(6) + str(a).zfill(6)
        P[i][3] = id
    P.sort(key=lambda x : (x[2]))
    for i in P:
        print(i[3])
    return
if __name__ == "__main__":
    main()

Solution (Python):

import math
import heapq
import bisect
import numpy as np


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

city = []
for i in range(M):
    p,y = map(int, input().split())
    city.append([i,p,y,0])

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

city[0][3] = 1
no = 2
for i in range(1,M):
    if city[i][1] != city[i-1][1]:
        no = 1
    city[i][3] = no
    no += 1

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

for c in city:
    print('{0:06d}{1:06d}'.format(c[1],c[3]))

Solution (Python):
N,M=map(int, input().split())
A=[[] for i in range(N)]
 
for i in range(M):
  p,y=map(int, input().split())
  A[p-1].append((y, i))
 
X=[0]*M
for i,d in enumerate(A):
  d.sort()
  for k,(y,j) in enumerate(d):
    X[j]=str(i+1).zfill(6)+str(k+1).zfill(6)
print(*X,sep='\n')

Solution (Python):

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

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

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

for i in range(m):
    cnt[l[i][0]]+=1
    s=str(l[i][0])
    i_str=str(cnt[l[i][0]])
    s_keta=len(s)
    i_keta=len(i_str)
    ans+=[['0'*(6-s_keta)+s+'0'*(6-i_keta)+str(cnt[l[i][0]]),l[i][-1]]]

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



for i in ans:
    print(i[0])

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

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

for i in range(1, m + 1):
    Pre[i - 1].append(i)

Pre.sort()

cnt = 1
Pre[0][1] = cnt
for i in range(1,m):
    if Pre[i - 1][0] != Pre[i][0]:
        cnt = 1
        Pre[i][1] = cnt
    else:
        cnt += 1
        Pre[i][1] = cnt

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

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

Solution (Python):
n,m=map(int,input().split())
pref=[[] for _ in range(n)]
ans=[]
for i in range(m):
  p,y=map(int,input().split())
  pref[p-1].append((i,p,y))
for i in range(n):
  pref[i].sort(key=lambda x: x[2])
  for j,t in enumerate(pref[i]):
    k,q,z=t
    s='0'*(6-len(str(q)))+str(q)+'0'*(6-len(str(j+1)))+str(j+1)
    ans.append((k,s))
ans.sort(key=lambda x: x[0])
for g,h in ans:
  print(h)

Solution (Python):
n, m = map(int, input().split())
name = []
city = []
prefecture = [1] * n
for i in range(m):
    a = list(map(int, input().split())) + [i+1]
    city.append(a)
    name.append("{}{}".format("0" * (6 - len(str(a[0]))), a[0]))
city_1 = sorted(city, key=lambda x: x[0])
city_sorted = sorted(city, key=lambda x: x[1])

x = 1
for i in range(m):
    p, y, num = city_sorted[i]
    x = prefecture[p-1]
    name[num-1] += "{}{}".format("0" * (6 - len(str(x))), x)
    prefecture[p-1] += 1
for i in name:
    print(i)

Solution (Python):
n,m=map(int,input().split())
a={}
s=[]
for i in range(m):
    p,y=map(int,input().split())
    if p not in a:
        a[p]=[]
    a[p].append(y)
    s.append((p,y))
b={}
for i in a.keys():
    a[i].sort()
    for j in range(len(a[i])):
        b[(i,a[i][j])]=j+1
for p,y in s:
    print(str(p).zfill(6)+str(b[(p,y)]).zfill(6))

Solution (Python):
N, M = map(int, input().split())
cities = {}
for m in range(M):
    p, y = map(int, input().split())
    if p not in cities:
        cities[p] = []
    cities[p].append([y, m])

ids = [None for _ in range(M)]
for city in sorted(cities.keys()):
    for idx, value in enumerate(sorted(cities[city])):
        year, m = value
        ids[m] = str(city).zfill(6) + str(idx + 1).zfill(6)

[print(id) for id in ids]

Solution (Python):
N, M = map(int, input().split())
NPM = [[0] * 3 for _ in range(M)]
for i in range(M):
    p, m = map(int, input().split())
    NPM[i][0] = i
    NPM[i][1] = p
    NPM[i][2] = m

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


city_num = [0] * N
ans_list = [""] * M
for i in range(M):
    city_num[NPM[i][1]-1] += 1

    ans_list[NPM[i][0]] = "{:0>6}{:0>6}".format(NPM[i][1], city_num[NPM[i][1]-1])

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

Solution (Python):
n,m = map(int, input().split())
pre = {}
city = []
for i in range(m):
    p,y = map(int, input().split())
    if p not in pre:
        pre[p] = []
    pre[p].append(y)
    city.append((p,y))

d = {}
for k in pre.keys():
    pre[k].sort()
    for i in range(len(pre[k])):
        d[(k, pre[k][i])] = i+1

for p,y in city:
    print(str(p).zfill(6) + str(d[(p, y)]).zfill(6))

Solution (Python):
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, m = na()
p = [[] for i in range(n)]
for i in range(m):
    pp, y = na()
    pp -= 1
    p[pp].append((y, i))

for i in range(n):
    if len(p[i]) <= 0:
        continue
    p[i].sort()

w = [0 for i in range(m)]
for i in range(n):
    if len(p[i]) <= 0:
        continue
    for j in range(len(p[i])):
        w[p[i][j][1]] = (i + 1, j + 1)

for i in range(m):
    print('{:0>6}{:0>6}'.format(w[i][0], w[i][1]))

Solution (Python):
import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict

N,M=map(int, input().split())
city = defaultdict(list)
p = [0] * M
y = [0] * M

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

year = defaultdict(list)
for key,v in city.items():
    for i,x in enumerate(sorted(v)):
        year[x] = i+1

for a in range(M):
    print(str(p[a]).zfill(6)+str(year[y[a]]).zfill(6))

Solution (Python):
def p_c():
    from collections import defaultdict
    from bisect import bisect
    n, m = map(int, input().split())
    py = [tuple(map(int, input().split())) for _ in range(m)]
    d = defaultdict(list)
    for p, y in py:
        d[p].append(y)
    for key in d.keys():
        d[key].sort()
    for p, y in py:
        print("{:06}{:06}".format(p, bisect(d[p], y)))
        
p_c()

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

py.sort(key=lambda x: (x[0],x[1]))
_dict = {}

ans=[]
for i in range(m):
    if not py[i][0] in _dict:
        _dict[py[i][0]]=1
    else:
        _dict[py[i][0]]+=1
    p="0"*(6-len(str(py[i][0])))+str(py[i][0])
    y="0"*(6-len(str(_dict[py[i][0]])))+str(_dict[py[i][0]])
    ans.append([p+y,py[i][2]])

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

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

dic = {i+1:[] for i in range(N)}

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

for i in range(N):
  dic[i+1].sort(key=lambda x:x[1])
  
ans = [0] * M
for k, vs in dic.items():
  order = 1
  for c, y in vs:
    ans[c] = (k, order)
    order += 1

for city, order in ans:
  print(str(city).zfill(6)+str(order).zfill(6))

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)
l1 = sorted(l)

check = 0
count = 1
for i in range(m):
    if l1[i][0] != check:
        check = l1[i][0]
        count = 1
        l1[i].append(count)
    else:
        count += 1
        l1[i].append(count)
l1.sort(key = lambda x: x[2])
for i in range(m):
    print("{:0>6}{:0>6}".format(l1[i][0],l1[i][3]))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()
 
def main():
    N,M=map(int,input().split())
    city=[[] for _ in range(N)]
    s=set()
    for i in range(M):
        P,Y=map(lambda x:int(x)-1,input().split())
        s.add(P)
        city[P].append((Y,i))
    city=list(map(sorted,city))
    ans=[0]*M
    for x in s:
        for i,c in enumerate(city[x]):
            ans[c[1]]=str(x+1).zfill(6)+str(i+1).zfill(6)
    for i in range(M):
        print(ans[i])
main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    city=[[] for _ in range(N)]
    s=set()
    for i in range(M):
        P,Y=map(lambda x:int(x)-1,input().split())
        s.add(P)
        city[P].append((Y,i))
    city=list(map(sorted,city))
    ans=[0]*M
    for x in s:
        for i,c in enumerate(city[x]):
            ans[c[1]]=str(x+1).zfill(6)+str(i+1).zfill(6)
    for i in range(M):
        print(ans[i])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
p_y = defaultdict(set)

N,M = map(int,input().split())
PY = [[int(x) for x in input().split()] for _ in range(M)]
for p,y in PY:
        p_y[p].add(y)

def set_rank(retu):
        return {x:i for i,x in enumerate(sorted(retu), 1)}

p_y = {p:set_rank(retu) for p,retu in p_y.items()}
for p,y in PY:
        print('{:06g}{:06g}'.format(p,p_y[p][y]))

Solution (Python):
import numpy as np
from itertools import accumulate

N, M = map(int, input().split())
P = []
p = [0] * (N+1)
for i in range(M):
    p1, y1 = map(str, input().split())
    p[int(p1)] += 1
    P.append(int(p1+y1.rjust(10,"0")))
    
ans = np.argsort(P)
ans = np.argsort(ans)
p = list(accumulate(p))

for i in range(M):
    a = P[i] // 10 ** 10 
    print(str(a).rjust(6,"0") + str(ans[i] - p[a-1] + 1).rjust(6,"0"))

Solution (Python):
N, M = map(int, input().split())
PYlist = [tuple(map(int, input().split())) for _ in range(M)]
from copy import deepcopy
PYsorted = sorted(deepcopy(PYlist))


def zero_ume(num: int) -> str:
    return (6 - len(str(num))) * "0" + str(num)


now_ken = -1
ans_dict = {}
now_num = 0
for p, y in PYsorted:
    if p != now_ken:
        now_num = 0
        now_ken = p
    now_num += 1
    ans_dict[(p, y)] = zero_ume(p) + zero_ume(now_num)

for py in PYlist:
    print(ans_dict[py])

Solution (Python):
n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(m)]
b=sorted(a)
id={}
t=1
for ind,i in enumerate(b):
    if ind!=0 and b[ind][0]!=b[ind-1][0]:
        t=1
    x=str(i[0]).zfill(6)
    y=str(t).zfill(6)
    t=int(t)
    t+=1
    idd=x+y
    id[str(i[0])+str(i[1])]=idd
for i in a:
    ii=str(i[0])+str(i[1])
    print(id[ii])