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):
n,m=[int(i) for i in input().split()]
id=[[int(i) for i in input().split()]+[j] for j in range(m)]

pre_num=[0]*(n+1)
ans=[""]*m

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

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

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

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

from copy import deepcopy


def main():
    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))
if __name__ == "__main__":
    main()

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

prefs_list = []
prefs_dict = {}
for i in range(m):
  p, y = map(int, input().split())
  prefs_list.append([p,y])
  if p in prefs_dict:
    prefs_dict[p].append(y)
  else:
    prefs_dict[p] = [y]

for key in prefs_dict:
  prefs_dict[key].sort()



for pref in prefs_list:
  print(str(pref[0]).zfill(6) + str(bisect.bisect_left(prefs_dict[pref[0]], pref[1])+1).zfill(6))

Solution (Python):

if __name__ == "__main__":
    N, M = map(int, input().split())
    city_list = []
    for i in range(M):
        city_list.append(list(map(int, input().split())))
    pref = {}
    pref_sort = {}
    for i in range(M):
        key = city_list[i][0]
        val = city_list[i][1]
        if str(key) in pref:
            pref[str(key)].append(val)
        else:
            pref[str(key)] = [val]
    ans = {}
    for key, val in pref.items():
        val.sort()
        for i in range(len(val)):
            ans[(key, val[i])] = str(key).zfill(6) + str(i+1).zfill(6)
    for key, val in city_list:
        print(ans[str(key), val])

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

for i,l in enumerate(list):
    list_pre[l[0]-1].append([l[1],i])

ans = []

for i,l in enumerate(list_pre):
    l.sort()
    for j,l2 in enumerate(l):
        ans.append([i+1,j+1,l2[1]])

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

for l in ans:
    print('%06d%06d' % (l[0],l[1]))

Solution (Python):
nm = input().split()
n = int(nm[0])
m = int(nm[1])
pylist = [input().split() for _ in range(m)]
yplist = [(int(py[1]), int(py[0]), i) for i, py in enumerate(pylist)]
yplist.sort()
city_counts = {}

anslist = {}

for y, p, i in yplist:
    if p not in city_counts:
        city_counts[p] = 0
    city_counts[p] += 1
    anslist[i] = '%06d%06d' % (p, city_counts[p])


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

Solution (Python):
def set_format(name: int):
    """6桁に揃える"""
    formated_name = "{:0=6}".format(name)
    return formated_name

def main():
    N, M = [int(c) for c in input().split()]
    lists = []
    for i in range(M):
        city = i
        prefecture, year = [int(c) for c in input().split()]
        id_ = ""
        lists.append([city, prefecture, year, id_])

    prefectures = [0] * (N + 1)

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

    for i in range(M):
        
        prefecture_name = lists[i][1]
        lists[i][3] = set_format(prefecture_name) + set_format(prefectures[prefecture_name] + 1)
        prefectures[prefecture_name] += 1

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

    for i in range(M):
        print(lists[i][3])

if __name__ =='__main__':
    main()

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    d = {}
    for i, (p, y) in enumerate(zip(P, Y)):
        d.setdefault(p, []).append((y, i))

    r = []
    for p, vs in d.items():
        r += [(n, "{:06}{:06}".format(p, i+1)) for i, (_, n) in enumerate(sorted(vs))]
    r.sort()

    return '\n'.join([c for _, c in r])


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))
    result = solve(N, M, P, Y)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
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[2])
d = defaultdict(int)
for i in range(m):
    d[city[i][1]] += 1
    city[i][3] = d[city[i][1]]
for _, p, _, x in sorted(city, key=lambda x:x[0]):
    print('%06d%06d' % (p, x))

Solution (Python):
import numpy as np
import copy
from operator import itemgetter

n,m=map(int,input().split())
l=[0]*m
for i in range(m):
    p,y=map(int,input().split())
    l[i]=[p*10**10+y,i,0]
buf=sorted(l,key=lambda x:x[0])
id=10**10
counter=1

for i in range(m):
    
    if id!=buf[i][0]//(10**10):
        id=buf[i][0]//(10**10)
        counter=1
    else:
        counter+=1
    buf[i][2]=id*10**6+counter
l=sorted(l,key=lambda x:x[1])
for i in range(m):
    print(str(0)*(12-len(str(l[i][2])))+str(l[i][2]))

Solution (Python):
import sys
_ = input()
PY = sorted([list(map(int, line.strip().split(' ')))+[i] for i,line in enumerate(sys.stdin)])
now_p = None
now_id = 0
for i in range(len(PY)):
  p,y,_ = PY[i]
  if now_p != p:
    now_p = p
    now_id = 1
  else:
    now_id += 1
  PY[i][1] = now_id
for p,id,i in sorted(PY, key=lambda x: x[2]):
  print('{:0>6}{:0>6}'.format(p,id))

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

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

    def set_rank(self, rank):
        self.rank = rank

    @property
    def id(self):
        return "{0:0>6}{1:0>6}".format(self.prefecture, self.rank)

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

rank_list = [1 for _ in range(N+1)]
for city in sorted(city_list, key=lambda city: city.year):
    prefecture = city.prefecture
    city.set_rank(rank_list[prefecture])
    rank_list[prefecture] += 1

for city in city_list:
    print(city.id)

Solution (Python):

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

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

c = 1
X_sort[0].append(str(X_sort[0][1]).zfill(6) + str(1).zfill(6))
for i,x in enumerate(X_sort[1:]):
    if x[1] == X_sort[i][1]:
        c += 1
        x.append(str(x[1]).zfill(6) + str(c).zfill(6))
    else:
        x.append(str(x[1]).zfill(6) + str(1).zfill(6))
        c = 1

Y = sorted(X_sort, key=lambda x:x[0])
for y in Y:
    print(y[3])

Solution (Python):
n, m = map(int, input().split())
cs = []
cd = {}
ps = {}
for _ in range(m):
  p, y = map(int, input().split())
  cs.append([p, y])
  if p in ps:
    ps[p].append(y)
  else:
    ps[p] = [y]
    
for p in ps:
  v = sorted(ps[p])
  for i, y in enumerate(v):
    cd[y] = i + 1
[print('{:06}{:06}'.format(c[0], cd[c[1]])) for c in cs]

Solution (Python):
N, M = map(int, input().split())
citys =[list(map(int, input().split())) for i in range(M)]
cs = {}
ans = {}
for p, y in citys:
    if p in cs:
        cs[p].append(y)
    else:
        cs[p] = [y]
for p, v in cs.items():
    v.sort()
    for i in range(len(v)):
        ans[(p, v[i])] = '0'*(6-len(str(p)))+str(p) + '0'*(6-len(str(i+1))) +str(i+1)
for p, y in citys:
    print(ans[(p, y)])

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

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

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

XX = []
p = None
n = 0
for x in X:
    if x[1] != p:
        p = x[1]
        n = 1
    else:
        n += 1
    XX.append(x + (n,))

XX.sort(key=lambda xx: xx[0])

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

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

n = 1
p = 0
ans = []
for city in sorted(cities, key = lambda x:(x[1],x[2])):
  if p != city[1]:
    n = 1
    p = city[1] 
  ans.append((city[0], city[1], n))
  n += 1

ans = sorted(ans)

for x in ans:
  print('{:06}{:06}'.format(x[1],x[2]))

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


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

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

city=city_list[0][1]
count=0
for i in range(m):
    if city == city_list[i][1]:
        count+=1
    else:
        city = city_list[i][1]
        count=1
    city_list[i].append(count)

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

for id in city_list:
    print(str(id[1]).zfill(6) + str(id[3]).zfill(6))

Solution (Python):
import sys
import bisect
input = sys.stdin.readline
N, M = map(int, input().split())
p_list = [[] for _ in [0]*(N+1)]
q_list = []
for _ in [0]*M:
    p,y = map(int, input().split())
    q_list.append((p,y))
    p_list[p].append(y)
p_list = [sorted(y_list) for y_list in p_list]
for p,y in q_list:
    x = bisect.bisect_left(p_list[p],y)
    ans = "%06d%06d"%(p,x+1)
    print(ans)

Solution (Python):
n,m = map(int,input().split())
p,y = [],[]
for i in range(m):
    v1,v2 = map(int,input().split())
    p.append(v1)
    y.append(v2)
    
py = zip(p,y,range(m))
py = sorted(py)
p,y,index = zip(*py)
 
ans = []
start = p[0]
count = 1
for i in range(m):
    if start == p[i]:
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1
    else:
        count = 1
        start = p[i]
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1
 
ans = zip(index,ans)
ans = sorted(ans)
index,ans = zip(*ans)
for i in ans:
    print(i)

Solution (Python):
def main():
  N,M = map(int, input().split())
  
  PY = []
  for _ in range(M):
    PY.append(list(map(int,input().split())))  
  id = 1
  for row in PY:
    row.append(id)
    id += 1
  
  PY.sort(key = lambda x: (x[0], x[1]))
  

  tempP = 0
  for row in PY:
    if row[0] != tempP: 
      id = 1
    row.append(id)
    id += 1
    tempP = row[0]
  
  PY.sort(key = lambda x: x[2])
  

  for row in PY:
    print('{:0>6}{:0>6}'.format(row[0],row[3]))
  
main()

Solution (Python):
n,m = map(int,input().split())
p,y = [],[]
for i in range(m):
    v1,v2 = map(int,input().split())
    p.append(v1)
    y.append(v2)
    
py = zip(p,y,range(m))
py = sorted(py)
p,y,index = zip(*py)

ans = []
start = p[0]
count = 1
for i in range(m):
    if start == p[i]:
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1
    else:
        count = 1
        start = p[i]
        ans.append(str(p[i]).zfill(6) + str(count).zfill(6))
        count += 1

ans1 = zip(index,ans)
ans1 = sorted(ans1)
index,ans = zip(*ans1)
for i in ans:
    print(i)

Solution (Python):
N,M=map(int,input().split())
A=[]  
B=[]
for i in range(M) :
  L=list(map(int,input().split()))
  A.append(L)
  B.append(L)
B.sort()
P=1
Q=1
for m in range(M):
  if B[m][0]==P :
    B[m].append(Q)
  else :
    Q=1
    B[m].append(Q)
  P=B[m][0]
  Q+=1
for i in A :
  X=str(i[0])
  Y=str(i[2])
  print("0"*(6-len(X))+X+"0"*(6-len(Y))+Y)

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

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

l.sort(key=itemgetter(1, 2))
res = []
idx, pre_p, y = l[0]
count = 1
res.append([idx, str(pre_p).zfill(6) + str(count).zfill(6)])
for idx, p, y in l[1:]:
    if pre_p == p:
        count += 1
    else:
        count = 1
    
    res.append([idx, str(p).zfill(6) + str(count).zfill(6)])
    pre_p = p

res.sort(key=itemgetter(0))
for idx, n in res:
    print(n)

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

PY = [tuple([i] + list(map(int,input().split(' ')))) for i in range(1,M+1)]
sorted1_PY = sorted(PY,key=lambda x:(x[1],x[2]))


prefecture = None
number = 1
sorted2_PY = []
for b,c,d in sorted1_PY:
  if  c!= prefecture:
    number = 1
    sorted2_PY.append((number,b,c,d))
    prefecture = c
  else:
    number += 1
    sorted2_PY.append((number,b,c,d))
    prefecrure = c

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

for a,b,c,d in sorted3_PY:
  prefecture = c
  number =  a
  print((str(c).rjust(6, '0') + (str(a).rjust(6, '0'))))

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

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

for k,v in d.items():
    d[k]=list(enumerate(sorted(v)))
d2=defaultdict(int)
for k,v in d.items():
    for s,t in v:
        d2[(k,t)]=s+1
for i in l:
    print(str(i[0]).zfill(6)+str(d2[tuple(i)]).zfill(6))

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


b = 0
c = []
pre = -1
for i in range(M):
  if PY[i][0] != pre:
    b = 0
  pre = PY[i][0]
  b += 1
  c.append([PY[i][2], "{0}{1}".format(str(PY[i][0]).zfill(6), str(b).zfill(6))])


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

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

P_years = {}

for i in range(1,M+1):
    P,Y = map(int, input().split())
    Pi.append(P)
    Yi.append(Y)
    if P not in P_years.keys():
        P_years[P] = [(i,Y)]
    else:
        P_years[P].append((i,Y))

cities_order = [-1]*(M+1)
for k in P_years.keys():
    cities = sorted(P_years[k], key=lambda x: x[1])
    for j, city in enumerate(cities):
        cities_order[city[0]] = j+1

for j, p in enumerate(Pi):
    print("{:06}{:06}".format(p, cities_order[j+1]))

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

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

results = []
for p, y, i in py:
    x = cnt.get(p, 0) + 1
    results.append(("{:06d}{:06d}".format(p, x), i))
    cnt[p] = x
results.sort(key=lambda x: x[1])
for ans, _ in results:
    print(ans)

Solution (Python):
import sys
 
s2nn = lambda s: [int(c) for c in s.split(' ')]
 
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
 
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
 
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
 
def main(N, M, PYm):
    
    
    dic = {}
    
    
    
    
    dic2tmp = {}
    for p in range(N+1):
        dic[p] = {}
        
        dic2tmp[p] = []
    for p, y in PYm:
        dic2tmp[p].append(y)
    for p in range(N+1):
        dic2tmp[p].sort()
        nby = [(i+1, y) for i, y in enumerate(dic2tmp[p])]
        
        for nb, y in nby:
            dic[p][y] = nb
    
    for p, y in PYm:
        nb = dic[p][y]
        print('%06d%06d' % (p, nb))

N, M = i2nn()
PYs = ss2nnn(ii2ss(M))
main(N, M, PYs)

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[0]*1000000000+x[1])
cnt=0
for i,x in enumerate(l):
    if x[0]!=l[i-1][0]:cnt=0
    cnt+=1
    l[i][1]=cnt
for x in sorted(l,key=lambda x:x[2]):
    print("{:06}{:06}".format(x[0],x[1]))

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):
from operator import itemgetter

n, m= map(int, (input().split()))
pyi = [list(map(int, (input().split()))) + [i] for i in range(m)]
pyi.sort(key=itemgetter(1))
pyi.sort(key=itemgetter(0))
cityflag = 0
ans = []
for rep in range(m):
    if pyi[rep][0] != pyi[rep - 1][0]:
        cityflag = 0

    cityflag += 1
    ans += [[pyi[rep][0] , cityflag, pyi[rep][2]]]

for i in sorted(ans, key=itemgetter(2)):
    print(str(i[0]).zfill(6) + str(i[1]).zfill(6))

Solution (Python):
N, M = map(int, input().split())
PY = []
for i in range(M):
    PY.append(list(map(int, input().split())) + [i])
    
PY.sort(key = lambda x:x[1])
PY.sort(key = lambda x:x[0])
    
bef = 0
state = 0
retstr = ''
triple = []
for i in PY:
    if (i[0] != bef):
        bef = i[0]
        state = 1
        triple.append([i[0], i[1], i[2], str(i[0]).rjust(6, '0') + str(state).rjust(6, '0')])
    else:
        state += 1
        triple.append([i[0], i[1], i[2], str(i[0]).rjust(6, '0') + str(state).rjust(6, '0')])
triple.sort(key = lambda x:x[2])
for i in triple:
    print(i[3])

Solution (Python):
from collections import defaultdict

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

rev_list = {}
for P, Y in years.items():
    Y.sort()
    rev_list[P] = {}
    for i in range(len(Y)):
        rev_list[P][Y[i]] = i + 1

for q in Q:
    print('{:06}{:06}'.format(q[0], rev_list[q[0]][q[1]]))

Solution (Python):
n,m = map(int,input().split())
py = {}
for i in range(m):
    p,y = map(int,input().split())
    py[i] = [p,y]
ans = sorted(py.items(),key=lambda x:x[1])


count = 1
ans[0][1].append(count)

for i in range(1,m):
    if ans[i][1][0] == ans[i-1][1][0]:
        count += 1
    else:
        count = 1
    ans[i][1].append(count)

ans = sorted(ans)

for i in range(m):
    a = "{0:06d}".format(ans[i][1][0])
    b = "{0:06d}".format(ans[i][1][2])
    print(a,end="")
    print(b)

Solution (Python):
n,m=map(int,input().split())
l=[[]for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  l[a-1]+=[[i,a,b]]
for a in range(n):
  l[a].sort(key=lambda x:x[2])
  for i in range(len(l[a])):
    l[a][i][2]=i+1
ll=[]
for i in range(n):
  ll+=l[i]
ll.sort(key=lambda x:x[0])
for i,a,b in ll:
  print("0"*(6-len(str(a)))+str(a)+"0"*(6-len(str(b)))+str(b))

Solution (Python):

N,M = map(int,input().split())
PY = [list(map(int,input().split()))+ [i] for i in range(M)]
    
def create(x):
    a = str(x)
    a = list(a)
    n = len(a)
    s = ['0'] * (6-n) + a
    s = ''.join(s)
    return s

ans = [0] * M
PY.sort()
idx = 1
flag = False
for i in range(M):
    if i > 0 and PY[i][0] != PY[i-1][0] : idx = 1
    ans[PY[i][2]] = create(PY[i][0]) + create(idx)
    idx += 1
    
for a in ans:
    print(a)

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())
y = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
    y[i].insert(0, i)
y.sort(key=itemgetter(2))
y.sort(key=itemgetter(1))
ans = []
tmp = 0
for i in range(M):
    if y[i][1] != y[i-1][1]:
        tmp = 0
    tmp += 1
    shita = str(tmp).zfill(6)
    ue = str(y[i][1]).zfill(6)
    ans.append([y[i][0], ue + shita])
ans.sort(key=itemgetter(0))
for i in range(M):
    print(ans[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(key=lambda x:x[1])
pcount = {i:0 for i in range(1,N+1)}
ID = {i:"" for i in range(1,M+1)}

for i in range(M):
  pcount[PY[i][0]] += 1
  PY[i].append("{:0=6}".format(PY[i][0]) + "{:0=6}".format(pcount[PY[i][0]]))
PY.sort(key=lambda x:x[2])
for i in range(M):
  print(PY[i][3])

Solution (Python):
n,m = map(int,input().split())
ans = [ "" for i in range(m) ]
data = []
for i in range(m):
    a,b = map(int,input().split())
    data.append([b,a,i])
data = sorted(data)
cnt = [ 1 for i in range(n+1) ]
for i in data:
    a = "0"*(6-len(str(i[1]))) + str(i[1]) + "0" * (6-len(str(cnt[i[1]]))) + str(cnt[i[1]])
    ans[i[2]] = a
    cnt[i[1]] += 1

for i in ans:
    print(i)

Solution (Python):
from operator import itemgetter
import collections
import math
import sys
import itertools
N,M = map(int,input().split())
nums = []
for i in range(M):
    P,Y = map(int,input().split())
    nums.append([P,Y,i])
nums.sort(key=itemgetter(1))
counter = collections.defaultdict(int)
anss= []
for i in nums:
    counter[i[0]]+=1
    ans = str(i[0]).zfill(6)+str(counter[i[0]]).zfill(6)
    anss.append([ans,i[2]])
anss.sort(key=itemgetter(1))
for ans in anss:
    print(ans[0])

Solution (Python):
n, m = map(int, input().split())
pys = [list(map(int, input().split())) for _ in range(m)]
map_ = {}
for i, (p, y) in enumerate(pys):
    map_.setdefault(p, [])
    map_[p].append(i)

for val in map_.values():
    val.sort(key=lambda i: pys[i][1])

ans = [None] * m
for key, val in map_.items():
    for num, i in enumerate(val):
        ans[i] = '{:06d}'.format(key) + '{:06d}'.format(num + 1)
for a in ans:
    print(a)

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

for i in range(m):
    if i==0 or p[i][0] != p[i-1][0]:
        cnt=1
    else:
        cnt+=1
    p[i].append(cnt)

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

for i in range(m):
    print("{:06}{:06}".format(p[i][0],p[i][3]))

Solution (Python):

import sys
from collections import defaultdict
from operator import itemgetter
INF = float("inf")


def solve(N: int, M: int, iPY):
    d = defaultdict(list)
    iPY.sort(key=itemgetter(2))
    for i, p, y in iPY:
        d[p].append([i, p, y])
    ans = []
    for k in d:
        for j, (i, p, y) in enumerate(d[k]):
            ans.append([i, "{0:06d}{1:06d}".format(p, j+1)])
    ans.sort()
    for a in ans:
        print(a[1])
    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))  
    iPY = [[]] * (M)
    for i in range(M):
        iPY[i] = [i, int(next(tokens)), int(next(tokens))]
    solve(N, M, iPY)


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split())
PY = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    PY[i].append(i)
PY.sort(key=lambda x:x[1])
ans = [0]*M
num = [0]*N
for p,y,i in PY:
    ans[i] = str(p).zfill(6) + str(num[p-1]+1).zfill(6)
    num[p-1] += 1
for s in ans:print(s)

Solution (Python):


class Prefecture():
    def __init__(self, i, P, Y):
        self.i = i
        self.P = P
        self.Y = Y
    
    def make_id(self, x):
        upper = str(self.P)
        while len(upper) < 6:
            upper = "0" + upper
        lower = str(x)
        while len(lower) < 6:
            lower = "0" + lower
        self.id = upper + lower            


def solve():
    N, M = list(map(int, input().split(" ")))
    prefectures = [None for i in range((N+1))]
    for i in range(M):
        p, y = list(map(int, input().split(" ")))
        if prefectures[p] is None:
            prefectures[p] = []
            prefectures[p].append(Prefecture(i, p, y))
        else:
            prefectures[p].append(Prefecture(i, p, y))

    
    ans = []
    for i in range(1, N+1):
        if prefectures[i] is None:
            continue

        prefectures[i].sort(key=lambda x: x.Y)
        for j in range(len(prefectures[i])):
            prefectures[i][j].make_id(j+1)
            ans.append(prefectures[i][j])
    
    
    ans.sort(key=lambda x: x.i)

    for prefecture in ans:
        print(prefecture.id)


if __name__ == "__main__":
    solve()

Solution (Python):

import sys
import copy
from bisect import bisect_left

def main():
	N, M = map(int, input().split(" "))
	data_org = []
	for _ in  range(M):
		p, y = map(int, input().split(" "))
		data_org.append((y, p))
		
	data_tmp = copy.copy(data_org)
	data_tmp.sort()
	
	counts = [0 for _ in range(N)]
	ans = []
	for i, val in enumerate(data_tmp):
		y, p = val
		p_zero = str(p).zfill(6)
		no = counts[p-1] + 1
		no_zero = str(no).zfill(6)
		counts[p-1] += 1
		
		ans.append(p_zero + no_zero)
		
	for i, val in enumerate(data_org):
		y, p = val
		tmp = bisect_left(data_tmp, (y, p))
		print(ans[tmp])
	
	
if __name__ == "__main__":
	main()

Solution (Python):
N,M=map(int, input().split())
py=[list(map(int, input().split())) for _ in range(M)]
cnt=[0]*(N+1)
ids={}
for p,y in sorted(py, key=lambda x: x[1]):
	cnt[p] += 1
	ids[y] = "%06d%06d" % (p, cnt[p])
for _,y in py:
	print(ids[y])

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

PY = [[0,0,0,0] for i in range(M)] 

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

PY.sort(key=lambda x:x[2])
cnt = [0]*(N+1)

for m in range(M):
    cnt[PY[m][1]] += 1
    PY[m][3] = cnt[PY[m][1]]

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

for m in range(M):
    print(str(PY[m][1]).zfill(6) + str(PY[m][3]).zfill(6))

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

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

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

number = []
for i in range(M):
    if i == 0:
        ct = 1
        number.append((str(py[i][0]).zfill(6) + str(ct).zfill(6), py[i][2]))
    else:
        if py[i-1][0] == py[i][0]:
            ct += 1
            number.append((str(py[i][0]).zfill(6) + str(ct).zfill(6), py[i][2]))
        else:
            ct = 1
            number.append((str(py[i][0]).zfill(6) + str(ct).zfill(6), py[i][2]))

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

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

Solution (Python):
N, M = map(int, input().split())
py = []
for _ in range(M):
    py.append(list(map(int, input().split())))
d = {}
now = 0
num = 0
for p, y in sorted(py):
    if now != p:
        now = p
        num = 1
    d[(p, y)] = num
    num += 1
for p, y in py:
    print('{:06d}{:06d}'.format(p, d[(p, y)]))

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-1,y,i])



P_Y.sort() 

ans_P_Y = [] 
count = 1
for i in range(M):
  if(i != 0):
    if(P_Y[i-1][0] == P_Y[i][0]): count += 1
    else: count = 1
  ans_P_Y.append([P_Y[i][2],P_Y[i][0]+1,count])
ans_P_Y.sort()

for i in range(M):
  ans = str(ans_P_Y[i][1]).zfill(6) + str(ans_P_Y[i][2]).zfill(6)
  print(ans)

Solution (Python):
n, m = map(int, input().split())
py = [list(map(int, input().split())) + [0] for _ in range(m)]
py_sorted = sorted(py, key=lambda x: x[1])
d = {}

for pyi in py_sorted:
    if pyi[0] not in d:
        d[pyi[0]] = 1
    else:
        d[pyi[0]] += 1
    pyi[2] = d[pyi[0]]

for pyi in py:
    print(str(pyi[0]).zfill(6) + str(pyi[2]).zfill(6))

Solution (Python):
import operator
def makecode(n):
	m = n
	s = str(n)
	while m < 100000:
		s = '0' + s
		m = m * 10
	return s
N, M = map(int, raw_input().split())
data = []
serial = []
for i in range(0, N):
	data.append([])
for i in range(0, M):
	P, Y = map(int, raw_input().split())
	data[P-1].append([i+1, Y])
for i in range(0, N):
	data[i].sort(key=operator.itemgetter(1))
for i in range(0, N):
	for j in range(0, len(data[i])):
		s = makecode(i+1) + makecode(j+1)
		serial.append([data[i][j][0], s])
serial.sort(key=operator.itemgetter(0))
for i in range(0, M):
	print serial[i][1]

Solution (Python):
N,M = list(map(int,input().split()))
PY = []
DD = [0 for i in range(N+1)]
for i in range(M):
    P,Y = list(map(int,input().split()))
    PY.append((P,Y,i,""))
PY.sort()
DY = []
for i in PY:
    DY.append((i[2],str(i[0]).zfill(6) + str(DD[i[0]]+1).zfill(6)))
    DD[i[0]] = DD[i[0]] + 1
DY.sort()
for i in DY:
    print(i[1])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]


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

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

pref = {}

for i in range(M):

    if P[i] not in pref:
        pref[P[i]] = []

    pref[P[i]].append({
        'city': i,
        'year': Y[i],
    })

for key in pref:
    pref[key].sort(key=lambda x: x['year'])



city = {}

for key in pref:
    for i in range(len(pref[key])):
        city[pref[key][i]['city']] = {'order': i + 1}




for i in range(M):
    print(format(P[i], '06d') + format(city[i]['order'], '06d'))

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, M = map(int,input().split())
cities = []
for i in range(M):
    p, y = map(int,readline().split())
    temp = [p, y, i]
    cities.append(temp)
id = [1 for i in range(N)] 
sortedcities = sorted(cities, key=lambda x:x[1])
for i in range(M):
    sortedcities[i].append(id[sortedcities[i][0]-1])
    id[sortedcities[i][0]-1] += 1
originalcities = sorted(sortedcities, key=lambda x:x[2])
for i in range(M):
    write(str(originalcities[i][0]).zfill(6) + str(originalcities[i][3]).zfill(6) + "\n")

Solution (Python):
N, M = map(int, input().split())
P_Y_i = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
    P_Y_i[i].append(i)
Ken_index = [[] for i in range(N)]

for i in range(M):
    Ken_index[P_Y_i[i][0] - 1].append(P_Y_i[i])
for i in range(N):
    if len(Ken_index[i]) != 0:
        Ken_index[i].sort(key=lambda x: x[1])

Ken_Update = []
for Ken in Ken_index:
    for i in range(len(Ken)):
        Ken_Update.append(['{0:06d}'.format(Ken[i][0]) + '{0:06d}'.format(i+1), Ken[i][2]])

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

for i in range(len(Ken_Update)):
    print(Ken_Update[i][0])