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



Sample input:
2 3
1 32
2 63
1 12


Sample output:
000001000002
000002000001
000001000001

Submission status: Accepted

Solution code:
import sys
import math
from bisect import bisect_right
def main():
    N,M = map(int,input().split())
    Marray=[(0,0)] * M
    P={}
    for i in range(M):
        s = input().split()
        p=int(s[0])
        y=s[1]
        #print(s)
        if p in P.keys():
            P[p].append(int(y))
        else:
            P[p]=[]
            P[p].append(int(y))
        Marray[i]=(p,int(y))
        #print(P[p])
        
    for key in P:
        #string=P[key]
        
       # print(str)
        #sp=string.split(",")
        #de=len(sp)-1
        #del sp[de]
        #print(sp)
        tmp=sorted(P[key],key=int)
        #int_list=list(map(int,tmp))
        P[key]=tmp
        
        #print(P[key])
    
    for index,value in Marray:
        List=P[index]
        
        #print(list)
        result=bisect_right(List,value)
        result=str(result)
        index=str(index)
        index_zero = index.zfill(6)
        result_zero = result.zfill(6)
        print(index_zero,result_zero,sep='')



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
L=[]
for i in range(m):
    l=[i]+list(map(int,input().split()))+[0]
    L.append(l)
LS=sorted(L,key=itemgetter(1,2))
LS[0][3]=1
for i in range(m-1):
    if LS[i+1][1]==LS[i][1]:
        LS[i+1][3]=LS[i][3]+1
    else:
        LS[i+1][3]=1
LSS=sorted(LS,key=itemgetter(0))
for i in range(m):
    print(str(LSS[i][1]).zfill(6)+str(LSS[i][3]).zfill(6))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
# pyに入力の順番も一緒に記録しておく。
py = [list(map(int,input().split()))+[i] for i in range(m)]

#まずソート
py.sort()
#print(py) [[1, 12, 2], [1, 32, 0], [2, 63, 1]]

#id生成関数. 00000p00000y
def id(p_num,y_num):
  p_num,y_num = str(p_num),str(y_num)
  n1 = len(p_num)
  n2 = len(y_num)
  str_id = "0"*(6-n1)+str(p_num)+"0"*(6-n2)+str(y_num)
  return str_id
  
ID = [[] for _ in range(m)]
#初期値 [['000001000001', 2], [], []]
ID[0] = [id(py[0][0],1), py[0][2]] 
#print(ID)

#ソートしたものを、前から[ココ, , ]を見ながらID作る
cnt = 1
for i in range(1,m):
  #前と同じ県なら
  if py[i-1][0] == py[i][0]:
    cnt += 1
    ID[i] = [id(py[i][0],cnt), py[i][2]]
  else:
    cnt = 1
    ID[i] = [id(py[i][0],cnt), py[i][2]]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))

p_ys = []
for _ in range(M):
    p, y = map(int, input().split(' '))
    p -= 1
    p_ys.append([p, y])

counts = [1 for _ in range(N)]
order_dicts = [{} for _ in range(N)]
for p, y in sorted(p_ys, key=lambda x: x[1]):
    order_dicts[p][y] = counts[p]
    counts[p] += 1

for p, y in p_ys:
    print('%06d%06d' % (p+1, order_dicts[p][y]))

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
iPY = [0]*M
res = [0]*M
for i in range(M):
    P, Y = map(int, input().split())
    iPY[i] = (i, P, Y)
iPY.sort(key=itemgetter(2))
iPY.sort(key=itemgetter(1))
j = 1
p = iPY[0][1]
for i, P, Y in iPY:
    if P != p:
        j = 1
        p = P
    res[i] = "{:06}{:06}".format(P, j)
    j += 1
for s in res:
    print(s)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    l.sort()

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

l.sort()

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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

    #sort p
    py_list = sorted(py_list)

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

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

    for m in range(M):
        p = py_list[m][0]
        x = py_list[m][3]
        print("{:06}".format(p) + "{:06}".format(x))
    
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, M, P, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

for tup in sorted_dict:

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 2019-11-11 14:35:02(JST)
import sys
# import collections
import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
from copy import deepcopy

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N , M = map(int,input().split())
birth = []
for i in range(M):
    a , b = map(int,input().split())
    birth.append([a,b,i])
#print(birth)
work_list = sorted(birth,key=lambda x: x[1])
work_list.sort()
#print(birth)
lower = 1
ans = []
for i in range(1,len(birth)):
    ans.append([work_list[i-1][2],str(work_list[i-1][0]).zfill(6) + str(lower).zfill(6)])
    if work_list[i][0] == work_list[i-1][0]:
        lower += 1
    else:
        lower = 1
ans.append([work_list[M - 1][2],str(work_list[M-1][0]).zfill(6) + str(lower).zfill(6)])
ans.sort()
for val in ans:
    print(val[1])

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

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

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

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,M=map(int, sys.stdin.readline().split())
P=[ [] for _ in range(N+1) ]  #Prefecture 県
Q=[]    #クエリー

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,M=map(int, sys.stdin.readline().split())
P=[ [] for _ in range(N+1) ]  #Prefecture 県
Q=[]    #クエリー

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

city_list = []

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

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

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

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

Submission status: Accepted

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

#元の市の番号を末尾に追加。
#（答えの出力時に直さないといけないため）
for i in range(m):
  si[i].append(i)
si.sort()

#番号追加済みの市をメモる
sicount=[0]*n

#各配列のさらに末尾に、番号を追加。
for i in range(m):
  nanbanme=sicount[si[i][0]-1]+1
  sicount[si[i][0]-1]+=1
  ninsiki=str(si[i][0]).zfill(6)+str(nanbanme).zfill(6)
  si[i].append(ninsiki)

from operator import itemgetter

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

Submission status: Accepted

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

dd = [""] * M

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect

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

a = defaultdict(list)

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

Submission status: Accepted

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

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

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

sortL = sorted(L)

ID = ""

order = 0

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import os, sys, re, math

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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



if __name__ == '__main__':
    slove()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

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

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

Submission status: Accepted

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