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 = map(int, input().split())
P_Y_list = [list(map(int, input().split())) + [i] for i in range(M)]
P_Y_list.sort(key=lambda x: x[1])
count_P = [0] * (N+1)


for idx, p_y in enumerate(P_Y_list):
    p = p_y[0]
    y = count_P[p_y[0]] + 1
    ans = str(p).zfill(6) + str(y).zfill(6)
    p_y += [ans]

    count_P[p_y[0]] += 1

P_Y_list.sort(key=lambda x: x[2])
for p_y in P_Y_list:
    print(p_y[3])

Solution (Python):
from sys import stdin
import bisect

def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [fetch_int_input() for _ in range(times)]


PREF, YEAR = 0, 1

N, M = fetch_int_input()
data = fetch_int_inputs(M)

pre_save = [[] for _ in range(N)]
for d in data:
    pre_save[d[PREF] - 1].append(d[YEAR])

for p in pre_save:
    p.sort()


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


for d in data:
    left = str(d[PREF]).zfill(6)
    right = str(index(pre_save[d[PREF] - 1], d[YEAR]) + 1).zfill(6)
    print(left+right)

Solution (Python):
n, m = map(int, input().split())
py = []
s = '000000'
for i in range(m):
    p, y = map(int, input().split())
    py.append([p, y, i])
py.sort(key=lambda py:(py[0],py[1]))

py[0].append(1)
for i in range(m-1):
    a = 1
    if py[i][0] == py[i+1][0]:
        py[i+1].append(py[i][3]+1)
    else:
        py[i+1].append(1)
        
py.sort(key=lambda py:(py[2]))

for j in range(len(py)):
    print((s+str(py[j][0]))[-6:]+(s+str(py[j][3]))[-6:])

Solution (Python):
n,m=map(int,input().split())
Y=[0]*m
P=[0]*m
for i in range(m):
    P[i],Y[i]=map(int,input().split())
yp=list(zip(Y,P,range(m)))
yp.sort()
underdigit=[0]*(n+1)
ans=[""]*m
for y,p,i in yp:
    underdigit[p]+=1
    ans[i]="%06d%06d" %(p,underdigit[p])
for a in ans:
    print(a)

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

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

lst2 = []
pref = 0
for v in lst:
    if pref != v[0]:
        cnt = 1
        pref = v[0]
    lst2.append(['{:0=6}{:0=6}'.format(v[0], cnt), v[2]])
    cnt += 1
lst2.sort(key=lambda x: x[1])

[print(lst2[i][0]) for i in range(m)]

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
PY = [[int(x) for x in input().split()] for _ in range(M)]
for j in range(M):
    PY[j].append(j)
PY.sort()
A = [1] * (N+1)
ans = ["s"] * M
for i in range(M):
    temp = PY[i]
    P, Y = temp[0], temp[1]
    a = str(P).zfill(6)
    b = str(A[P]).zfill(6)
    A[P] += 1
    ans[temp[2]] = a + b
for k in ans:
    print(k)

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

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

for i in range(N):
  L[i]=sorted(L[i], reverse=False, key=lambda x: x[1])
  for j in range(len(L[i])):
    ans[L[i][j][0]]=[i,j]
    
for i in range(M):
  a = str(ans[i][0]+1).zfill(6)+str(ans[i][1]+1).zfill(6)
  print(a)

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

for i, (p, y) in enumerate(PY):
  D[p-1].append((y, i))

ans = [None] * M
output = [[] for _ in range(M)]
for i, d in enumerate(D):
  d.sort()
  for k, (y, j) in enumerate(d):
    ans[j] = (i, k)

for i, k in ans:
  print('{}{}'.format(str(i+1).zfill(6), str(k+1).zfill(6)))

Solution (Python):
import sys
from operator import itemgetter
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, M = MAP()
Cities = []
for i in range(M):
	Cities.append([i, MAP()])

Pref = [[] for _ in range(N)]



for c in Cities:
	i, [p, y] = c
	Pref[p-1].append([y, i])

for p in Pref:
	p.sort()


ans = []
for i,p in enumerate(Pref):
	for j in range(len(p)):
		ans.append([p[j][1] ,str(i+1).zfill(6)+str(j+1).zfill(6)])
ans.sort()

for a in ans:
	print(a[1])

Solution (Python):

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


d.sort(key=lambda x:x[1][1])
p_cnt = [0] * (n+1)
ret_tuples = [0] * m 

for i,v in enumerate(d):
    p = v[1][0]
    x = p_cnt[p]+1
    p_cnt[p]+=1
    ret_tuples[i] = (v[0],"{:0=6}{:0=6}".format(p,x))

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

Solution (Python):
n, m = map(int, input().split())
queue = []
for i in range(m):
    c, y= map(int, input().split())
    queue.append([c, y, i])

queue = sorted(queue)

index = 0
keep = queue[0][0]
for i in range(m):
    if keep != queue[i][0]:
        index = 0
        keep = queue[i][0]
    index += 1
    queue[i][0] = str(queue[i][0]).zfill(6)
    queue[i][1] = str(index).zfill(6)

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

for data in queue:
    cn, yn, i = data
    print(cn + yn)

Solution (Python):
n, m = map(int, raw_input().split())
prefecs = [[] for i in range(n+1)]
queries = []
for _ in range(m):
    p, y = map(int, raw_input().split())
    queries.append((p, y))
    prefecs[p].append(y)
for i in range(1, n+1):
    prefecs[i].sort()
dic_list = [{} for i in range(n+1)]
for i in range(1, n+1):
    for j in range(len(prefecs[i])):
        dic_list[i][prefecs[i][j]] = j+1
for p, y in queries:
    print "%06d%06d" % (p, dic_list[p][y])

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

PY.sort()
ans = [0 for i in range(M)]
count = 0
old = 0
for j in range(M):
    p,y,inum = PY[j]
    if old == p:
        pnum = p
        cnum = count
    else:
        old = p
        count = 1
        pnum = p
        cnum = 1

    count += 1
    pnum = str(pnum)
    cnum = str(cnum)
    ans[inum] = '0'*(6-len(pnum)) + pnum + '0'*(6-len(cnum)) + cnum

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

Solution (Python):
from collections import defaultdict
d = defaultdict(list)
n, m = map(int, input().split())
l = [0]*m
for i in range(m):
  p, y = map(int, input().split())
  d[p].append((y, i))
for p, b in d.items():
  b.sort()
  for i in range(len(b)):
    s, t = b[i]
    l[t] = "0"*(6-len(str(p))) + str(p) + "0"*(6-len(str(i+1))) + str(i+1)
print(*l, sep="\n")

Solution (Python):
N,M=map(int,input().split())
L=[[0 for i in range(4)]for i in range(M)]
for i in range(M):
    a,b=map(int,input().split())
    L[i][0]=i
    L[i][1]=a
    L[i][2]=b
L2=sorted(L,key= lambda x: (x[1],x[2]))

c=0
t=0
for i in range(M):
    if(L2[i][1]!=c):
        c=L2[i][1]
        t=1
    L2[i][3]=t
    t+=1

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

for i in range(M):
    print('{0:06d}'.format(L3[i][1]),'{0:06d}'.format(L3[i][3]),sep="")

Solution (Python):
from collections import defaultdict
N,M=map(int,input().split())
PD=defaultdict(lambda: [])
OR=dict()
ANS=dict()
for i in range(M):
    p, y=map(int,input().split())
    OR[i] = (p,y)
    PD[p].append(y)

for k in PD.keys():
    l=sorted(PD[k])
    for i,n in enumerate(l):
        ANS[(k,n)] = str(k).zfill(6) + str(i+1).zfill(6)
for k in OR.values():
    print(ANS[k])

Solution (Python):
from collections import defaultdict
N,M=map(int,input().split())
PD=defaultdict(lambda: [])
OR=dict()
ANS=dict()
for i in range(M):
    p, y=map(int,input().split())
    OR[i] = (p,y)
    PD[p].append(y)

for k in PD.keys():
    l=sorted(PD[k])
    for i,n in enumerate(l):
        ANS[(k,n)] = str(k).zfill(6) + str(i+1).zfill(6)
for k in OR.values():
    print(ANS[k])

Solution (Python):
from collections import defaultdict
N, M = [int(val) for val in input().split(' ')]
P, Y = [], []


def complete_val(val):
    length = len(str(val))
    prefix = '0' * (6 - length)
    return prefix + str(val)


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

cities = defaultdict(dict)
for i in range(M):
    cities[P[i]][i] = Y[i]

results = {}
for p, p_cities in cities.items():
    p_str = complete_val(p)
    for city_rank, (m_index, year) in enumerate(sorted(p_cities.items(), key=lambda x: x[1])):
        city_str = complete_val(city_rank+1)
        results[m_index] = p_str + city_str

for m_index, string in sorted(results.items(), key=lambda x: x[0]):
    print(string)

Solution (Python):
N,M=map(int,input().split())
PY=[list(map(int,input().split())) for _ in range(M)]
idx=sorted(range(M),key=lambda x:PY[x][1])
PY.sort(key=lambda x:x[1])
flag=[1]*N
keep=[]
for P,Y in PY:
  keep.append(str(P).zfill(6)+str(flag[P-1]).zfill(6))
  flag[P-1]+=1
  
ans=[0]*M
for i,k in zip(idx,keep):
  ans[i]=k
  
for a in ans:
  print(a)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
p = []
res = [[] for i in range(m)]
for i in range(m):
    a,b = inpl()
    p.append((a,b,i))
p.sort()
cnt = 0
tmp = 0
for i,j in enumerate(p):
    if i == 0:
        tmp = j[0]
    if tmp == j[0]:
        cnt += 1
    else:
        tmp = j[0]
        cnt = 1
    res[j[2]] = [j[0],cnt] 
for i in res:
    print('{}{}'.format(str(i[0]).zfill(6),str(i[1]).zfill(6)))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
p = []
res = [[] for i in range(m)]
for i in range(m):
    a,b = inpl()
    p.append((a,b,i))
p.sort(key=lambda x:x[1])
p.sort(key=lambda x:x[0])
cnt = 0
tmp = 0
for i,j in enumerate(p):
    if i == 0:
        tmp = j[0]
    if tmp == j[0]:
        cnt += 1
    else:
        tmp = j[0]
        cnt = 1
    res[j[2]] = [j[0],cnt] 
for i in res:
    print('{}{}'.format(str(i[0]).zfill(6),str(i[1]).zfill(6)))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
py = [inpl() for i in range(m)]
p = [[] for i in range(n+5)]
res = defaultdict(lambda : defaultdict(int))
for i,j in enumerate(py):
    p[j[0]].append(j[1])
for k,i in enumerate(p):
    i.sort()
    for j,_ in enumerate(i):
        res[k][i[j]] = j+1
for i in py:
    print('{0}{1}'.format(str(i[0]).zfill(6),str(res[i[0]][i[1]]).zfill(6)))

Solution (Python):

N,M = map(int,input().split())
PY = []

for i in range(M):
    p,y = map(int,input().split())
    PY.append([p,y,i])
    
ans = 0
PY.sort()
ans = ["" for i in range(M)]
count = 0
old = 0
for py in PY:
    p,y,i = py
    if old == p:
        city = p
        num = count
        sc = str(city)
        sn = str(num)
        while len(sc) < 6:
            sc = "0"+sc
        while len(sn) < 6:
            sn = "0"+sn
        ans[i] = sc+sn
        count+=1
    else:
        count = 1
        old = p
        city = p
        num = count
        sc = str(city)
        sn = str(num)
        while len(sc) < 6:
            sc = "0"+sc
        while len(sn) < 6:
            sn = "0"+sn
        ans[i] = sc+sn
        count+=1
        
for i in range(M):
    print(ans[i])

Solution (Python):
from collections import defaultdict
from bisect import bisect
N,M,*P = map(int,open(0).read().split())
d = defaultdict(list)
Z = set()
for n,m in zip(*[iter(P)]*2):
    d[n].append(m)
    Z.add(n)
for z in Z:
    d[z].sort()
for n,m in zip(*[iter(P)]*2):
    print(str(n).zfill(6)+str(bisect(d[n],m)).zfill(6))

Solution (Python):



def main():
    from bisect import bisect_left
    import sys

    input = sys.stdin.readline

    n, m = map(int, input().split())
    PY = []
    e = [[] for _ in range(n + 1)]
    for _ in range(m):
        _p, _y = map(int, input().split())
        e[_p].append(_y)
        PY.append((_p, _y))

    for idx in range(n + 1):
        e[idx] = tuple(sorted(set(e[idx])))

    for p, y in PY:
        id = bisect_left(e[p], y)
        print('{:06d}{:06d}'.format(p, id + 1))


if __name__ == '__main__':
    main()

Solution (Python):



from bisect import bisect_left

n, m = map(int, input().split())
PY = []
e = [[] for _ in range(n + 1)]
for _ in range(m):
    _p, _y = map(int, input().split())
    e[_p].append(_y)
    PY.append((_p, _y))

for idx in range(n + 1):
    e[idx] = tuple(sorted(set(e[idx])))

for p, y in PY:
    id = bisect_left(e[p], y)
    print('{:06d}{:06d}'.format(p, id + 1))

Solution (Python):
N,M = map(int,input().split())
X=[]
for i in range(M):
  p,y = map(int,input().split())
  X +=[[i,p,y,0]]
X=sorted(X,key=lambda x:x[2])
R=[0]*(N+1)
for i in range(M):
  X[i][3]=R[X[i][1]]+1
  R[X[i][1]] += 1
X=sorted(X,key=lambda x:x[0])
for i in range(M):
  id_A='0'*(6-len(str(X[i][1])))+str(X[i][1])
  id_B='0'*(6-len(str(X[i][3])))+str(X[i][3])
  print(id_A+id_B)

Solution (Python):
import heapq
n,m=map(int,input().split())
a=[0]*n
b=[]
c=[]


def make_num_str_pair(s):
    return str(s[0]).zfill(6)+str(s[1]).zfill(6)


for i in range(m):
    p,y=map(int,input().split())
    b.append([p,y,i])
b.sort(key=lambda x: x[1])
for i in range(m):
    a[b[i][0]-1]+=1
    b[i][1]=a[b[i][0]-1]
b.sort(key=lambda x: x[2])
for i in range(m):
    print(make_num_str_pair(b[i]))

Solution (Python):
from bisect import bisect_left
N,M = map(int,input().split())
PtoY = [[] for n in range(N)]
check = []
for m in range(M):
    P,Y = map(int,input().split())
    PtoY[P-1].append(Y)
    check.append([P,Y])
for n in range(N):
    PtoY[n].sort()
for m in range(M):
    p,y = check[m][0],check[m][1]
    a = bisect_left(PtoY[p-1],y)+1
    string = str(p).zfill(6) + str(a).zfill(6)
    print(string)

Solution (Python):
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,M = MAP()
Y = [0]*(10**5)
P = [0]*(10**5)
yd =[[] for _ in range(N)]
for i in range(M):
    p,y = MAP()
    P[i] = p-1
    Y[i] = y
    yd[p-1].append(y)

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

for i in range(M):
    print("{0:06d}".format(P[i]+1),end="")
    print("{0:06d}".format(bisect.bisect_left(yd[P[i]],Y[i])+1))

Solution (Python):
n,m=map(int,input().split())
li=[]
ans=[]
cnt=0
for i in range(m):
    p,y=map(int,input().split())
    li.append([p,y,i])
li=sorted(li,key=lambda x:x[1])
li=sorted(li,key=lambda x:x[0])
pre=li[0][0]
for j in range(m):
    if li[j][0]==pre:
        cnt+=1
        ans.append([str(pre).zfill(6)+str(cnt).zfill(6),li[j][2]])
        
    else:
        pre=li[j][0]
        cnt=1
        ans.append([str(pre).zfill(6)+str(cnt).zfill(6),li[j][2]])

ans=sorted(ans,key=lambda x:x[1])
for k in range(m):
    print(ans[k][0])

Solution (Python):
from copy import deepcopy as dp
from operator import itemgetter as ig
n,m = map(int,input().split())

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

list2 = dp(list1)
list2.sort(key=ig(1,2))
city_number = 0
list2[0].append(city_number)
for i in range(1,m):
    if list2[i][1] == list2[i-1][1]:
        city_number += 1
        list2[i].append(city_number)
    else:
        city_number = 0
        list2[i].append(city_number)
list2.sort(key=ig(0))
for i in range(m):
    print("{0:06d}".format(list2[i][1])+"{0:06d}".format(list2[i][3]+1))

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

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

count = [0] * (N+1)

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

ans = [0] * M

for i in range(M):
    count[data[i][1]] += 1
    y = [0] * (6-len(list(str(data[i][1])))) + list(str(data[i][1]))
    z = [0] * (6-len(list(str(count[data[i][1]])))) + list(str(count[data[i][1]]))
    ans[data[i][0]] = list(map(int,y + z))


for i in range(M):
    print("".join(map(str,ans[i])))

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

prefecture = [[] for i in range(n)]
li = []

for i in range(m):
    a, b = map(int, input().split())
    li.append([a,b])
    prefecture[a-1].append(b)

for i in prefecture:
    i.sort()

for i in li:
    a = i[0]-1
    b = i[1]
    index = bisect.bisect_left(prefecture[a], b) + 1
    print(str(i[0]).zfill(6)+str(index).zfill(6))

Solution (Python):
from operator import itemgetter
N , M = map(int, input().split(' '))

city = []
for i in range(M):
    a, b = map(int, input().split(' '))
    city.append([a, b, i])

city_y = sorted(city, key = itemgetter(1))
city_num = [0 for _ in range(N+1)]
city_ID = {}

for i in range(M):
    city_num[city_y[i][0]] += 1
    city_ID[city_y[i][2]] = ("{:0=6}{:0=6}".format(city_y[i][0], city_num[city_y[i][0]]))

for i, j in sorted(city_ID.items()):
    print(j)

Solution (Python):

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time



def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()

def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)

YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False


def main():
    N, M = MI()
    cities = [None] * M
    identifiers = [1] * (N + 1)
    output = [None] * M

    for i in range(M):
        P, Y = MI()
        cities[i] = (Y, P, i)

    cities.sort()
    show(cities)

    for i in range(M):
        Y, P, idx = cities[i]
        output[idx] = str(P).zfill(6) + str(identifiers[P]).zfill(6)
        identifiers[P] += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
c = []
for i in range(M):
  p, y = map(int, input().split())
  c.append((p, y, i))
c.sort(key = lambda x: (x[0], x[1]))
table = [0] * (N + 1)
res = [None] * M
for i in range(M):
  p, y, j = c[i]
  table[p] += 1
  res[j] = str(p).zfill(6) + str(table[p]).zfill(6)
for i in range(M):
  print(res[i])

Solution (Python):
a,b = map(int,input().split())
li = []
for i in range(b):
    li.append(input().split())
for i in range(b):
    li[i] = [int(x) for x in li[i]]
    li[i].append(i+1)
li.sort()
L = []
for i in range(a):
    L.append([])
for i in range(b):
    L[li[i][0]-1].append((li[i][0],li[i][1],li[i][2]))
ans = []
for i in range(a):
    for j in range(len(L[i])):
        ans.append((L[i][j][0],j+1,L[i][j][2]))
ans.sort(key = lambda x:x[2])
for i in range(b):
    print(str(ans[i][0]).zfill(6)+str(ans[i][1]).zfill(6))

Solution (Python):
from operator import itemgetter
 
N, M = map(int,input().split())
data = [[int(i) for i in input().split()] for j in range(M)]
 

for i in range(M):
    data[i].insert(0,i)
 

data.sort(key=itemgetter(1,2))
 


answer = [[0,0] for i in range(M)]
x = 1

for i in range(M):
    answer[i][0] = data[i][0]
    if data[i][1] != data[i-1][1]:
        x = 1
    answer[i][1] = data[i][1]*1000000 + x
    x += 1
 

answer.sort(key=itemgetter(0))
for _,i in answer:
    print(str(i).rjust(12,"0"))

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

N, M = [int(x) for x in input().strip().split()]
NL = [deque([]) for n in range(10 ** 5)]

IN = [0] * M
d = {}
for m in range(M):
    IN[m] = tuple([int(x) for x in input().strip().split()]) 

for p, y in IN:
    NL[p-1].append(y)

for p, nl in enumerate(NL, start=1):
    d[p] = {}
    for i, n in enumerate(sorted(nl), start=1):
        d[p][n] = i

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

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

DEBUG = False

dbgp = print if DEBUG else lambda *x:x

rank = dict()
counter = dict([i, 1] for i in range(1, N + 1))
for p, y in sorted(PY, key= lambda x:x[1]):
    rank[y] = counter[p]
    counter[p] += 1

dbgp('rank : ', rank)
dbgp('counter : ', counter)

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

Solution (Python):
N,M=map(int,input().split())
info=[None]*M
pre=[None]*(N+1)
for i in range(M):
  p,y=map(int,input().split())
  info[i]=[p,y]
  if pre[p]==None:
    pre[p]=[y]
  else:
    pre[p].append(y)
    
for i in range(1,len(pre)):
  cities=pre[i]
  if cities==None:
    continue
  cities=sorted(cities)
  dic={}
  for j in range(len(cities)):
    dic[cities[j]]=j+1
  pre[i]=dic
  
for i in range(len(info)):
  p=info[i][0]
  y=info[i][1]
  print(str(p).zfill(6)+str(pre[p][y]).zfill(6))

Solution (Python):
N,M = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(M)]
new=[]
inf  = [u for u in range(1,N+1)]
ref = 0
for i in range(M):
  x[i].insert(0,i)
x.sort(key=lambda y: y[2])
x.sort(key=lambda y: y[1])

for q in inf:
  count = 1
  for p in range(ref,M):
    if x[p][1]!=q:
      ref=p
      break
    new.append([x[p][0],x[p][1]*1000000+(count)])
    count += 1
new.sort()
for z in range(M):
  takahasi = "%012d" % new[z][1]
  print(takahasi)

Solution (Python):
from collections import defaultdict
def inpl(): return list(map(int,input().split()))

class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

ui = defaultdict(CountUp())
plist = []
clists = []
Np = 0

N, M = inpl()
P = [0]*M
Y = [0]*M
for i in range(M):
    P[i], Y[i] = inpl()
    p = ui[P[i]]
    if p >= Np:
        plist.append(P[i])
        clists.append([[i,Y[i]]])
        Np += 1
    else:
        clists[p].append([i,Y[i]])

ids = ['']*M
for p in range(Np):
    clists[p].sort(key=lambda x: x[1])
    for c in range(len(clists[p])):
        cid = "{0:06d}".format(plist[p]) + "{0:06d}".format(c+1)
        ids[clists[p][c][0]] = cid

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

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

py_map = {}
x = 1
prep = 0
for p, y in sorted(PY):
    if prep == p:
        x += 1
    else:
        x = 1
    py_map[(p,y)] = str(p).zfill(6) + str(x).zfill(6)
    prep = p

for p, y in PY:
    print(py_map[(p, y)])

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

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

city = []

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

dic = defaultdict(list)
for p, y in sorted(city):
    dic[p] += [y]




for p, y in city:
    x = bisect(dic[p], y)
    print("{0:06d}{1:06d}".format(p, x))

Solution (Python):


from collections import namedtuple
from operator import attrgetter

City = namedtuple("City", "ID, pref, year")

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

Cities = []
for ID in range(M):
    pref, year = map(int, input().split())
    Cities.append(City(ID, pref, year))

def get_sID(Cities):
    temp = Cities.copy()

    temp.sort(key=attrgetter("year"))
    temp.sort(key=attrgetter("pref"))

    lid = 1
    currentPref = None
    for City in temp:
        if currentPref != City.pref:
            currentPref = City.pref
            lid = 1

        yield City.ID, "{0:0>6}{1:0>6}".format(City.pref, lid)
        lid += 1

for _, sID in sorted(get_sID(Cities)):
    print(sID)

Solution (Python):
from collections import defaultdict

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

d = defaultdict(int)
b = dict()

for p, y in sorted(years, key=lambda x: x[1]):
    d[p] += 1
    b[y] = '{:06d}{:06d}'.format(p, d[p])

for p, y in years:
    print(b[y])

Solution (Python):
n,m=map(int,input().split())
d=[]
for i in range(m):
  d.append(list(map(int,input().split())))
  d[i].append(1)
s=sorted(d)
k=1
if m>1:
  for i in range(m-1):
    if s[i][0]==s[i+1][0]:
      s[i][2]=k
      s[i+1][2]=k+1
      k=k+1
    else:
      k=1
      s[i+1][2]=k
      
for i in range(m):
  ans=1000000000000+d[i][0]*1000000+d[i][2]
  print(str(ans)[1:])

Solution (Python):
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=sorted(PY,key=lambda x: x[2])

k=list(range(1,10**5+1))
v=[0]*10**5
cnt_dict=dict(zip(k,v))
arr=[]
for i,j,k in PY_sort:
    cnt_dict[j]+=1
    arr.append([i,str(j).zfill(6)+str(cnt_dict[j]).zfill(6)])

s = sorted(arr, key=lambda x: x[0])
for a,b in s:
    print(b)

Solution (Python):
n,m=[int(i) for i in input().split()]
py=[[int(i) for i in input().split()]+[_,""] for _ in range(m)]
kazu=[0]*(n+1)
py.sort(key=lambda x:x[1])
for i in range(m):
    kazu[py[i][0]]+=1
    py[i][3]+=str(kazu[py[i][0]])
py.sort(key=lambda x:x[2])
for i in range(m):
    print(str(py[i][0]).zfill(6)+py[i][3].zfill(6))

Solution (Python):
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]
        
        if p in P.keys():
            P[p].append(int(y))
        else:
            P[p]=[]
            P[p].append(int(y))
        Marray[i]=(p,int(y))
        
        
    for key in P:
        
        
       
        
        
        
        
        tmp=sorted(P[key],key=int)
        
        P[key]=tmp
        
        
    
    for index,value in Marray:
        List=P[index]
        
        
        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()

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

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

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


py.sort()



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

ID[0] = [id(py[0][0],1), py[0][2]] 



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

Solution (Python):

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

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