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):
from __future__ import print_function

import sys
import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy,functools
import heapq
from heapq import heappush
from heapq import heappop
import random


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

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


l_pref=[[] for _ in range(n+1)]    
for i in range(1,m+1):
    l_pref[p[i]].append((y[i],i))
for i in range(1,n+1):
    l_pref[i].sort()




lll = [(1,1) for i in range(m+1)]
for i in range(1,n+1):
    for j in range(len(l_pref[i])):
        lll[l_pref[i][j][1]] = j+1


for i in range(1,m+1):
    
    print("0"*(6-len(str(p[i])))  +  str(p[i])  +  "0"*(6-len(str(lll[i]))) + str(lll[i]) )

Solution (Python):
import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

from operator import itemgetter

N, M = rs()
data = [[i]+[int(_) for _ in input().split()] for i in range(M)]

data.sort(key=itemgetter(1, 2))
ans = [''] * M

P = -1
cnt = 0
for d in data:
    if P != d[1]:
        P = d[1]
        cnt = 1
    else:
        cnt += 1
    ans[d[0]] = str(P).zfill(6) + str(cnt).zfill(6)

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

Solution (Python):
n,m = map(int, input().split())
Y = [[] for _ in range(n)]
for i in range(m):
    p,yi = map(int, input().split())
    Y[p-1].append((yi,i))
ans = [-1 for _ in range(m)]
for i,d in enumerate(Y):
    d.sort()
    for k,(a,b) in enumerate(d):
        ans[b] = str(i+1).rjust(6,"0") + str(k+1).rjust(6,"0")
for i in range(m):
    print(ans[i])

Solution (Python):
n,m = map(int, input().split())
Y = [[] for _ in range(n)]
for i in range(m):
    p,yi = map(int, input().split())
    Y[p-1].append((yi,i))
ans = [-1 for _ in range(m)]
for i,d in enumerate(Y):
    d.sort()
    for k,(a,b) in enumerate(d):
        ans[b] = str(i+1).rjust(6,"0") + str(k+1).rjust(6,"0")
print(*ans, sep = "\n")

Solution (Python):
class City:
  def __init__(self, born):
    self.born = born
    self.id = ''

class Pref:
  def __init__(self, id):
    self.id = str(id).zfill(6)
    self.cities = []
  
  def add_city(self, city):
    self.cities.append(city)
  
  def issue_ids(self):
    self.cities.sort(key=lambda c:c.born)
    for i, c in enumerate(self.cities):
      c.id = self.id + str(i+1).zfill(6)

      
prefs = dict()
cities = []
n, m = map(int, input().split())
for _ in range(m):
  p, y = map(int, input().split())
  city = City(y)
  cities.append(city)
  if p in prefs:
    prefs[p].add_city(city)
  else:
    pref = Pref(p)
    pref.add_city(city)
    prefs[p] = pref

for p in prefs.values():
  p.issue_ids()

for c in cities:
  print(c.id)

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

PY = []

Px = [0] * (N+1)
for i in range(M):
    p, y = [int(x) for x in input().split()]
    PY.append((i, p, y))

PY.sort(key=lambda x:x[2])
result = [None]*M
for i, p, y in PY:
    Px[p]+=1
    result[i] = "%06d%06d" % (p, Px[p])

for x in result:
    print(x)

Solution (Python):

import sys
import itertools


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):

    L = []
    R = [""] * M
    for p,y,i in zip(P,Y,range(M)):
        L.append((i,p,y))
    L.sort(key=lambda x: x[1]*10**10+x[2])

    for k,g in itertools.groupby(L,key=lambda x: x[1]):
        for i,gg in enumerate(g):
            R[gg[0]] = str(gg[1]).zfill(6) + str(i+1).zfill(6)

    for r in R:
        print(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))
    solve(N, M, P, Y)

if __name__ == '__main__':
    main()

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

p = [0]*(m)
y = [0]*(m)

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

b = [[p[i],y[i]] for i in range(0,m)]

a = sorted(b)
num = {}
count = 1
num[a[0][1]] = 1

for i in range(1,m):
    if a[i-1][0] == a[i][0]:
        count += 1
    else:
        count = 1    
    num[a[i][1]] = count

for i in range(0,m):
    z1 = 6 - len(str(b[i][0]))
    z2 = 6 - len(str(num[b[i][1]]))
    print("0"*z1 + str(b[i][0]) + "0"*z2 + str(num[b[i][1]]))

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

import collections, 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())
ans = []

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

ans = sorted(ans, key=itemgetter(1, 2))

_city = -1
for i in range(len(ans)):
    if _city != ans[i][1]:
        cnt_city = 1
        _city = ans[i][1]
    else:
        cnt_city += 1
    ans[i] += (cnt_city,)

ans.sort()

for _ans in ans:
    print(str(_ans[1]).zfill(6)+str(_ans[3]).zfill(6))

Solution (Python):

"""
C - ID
https://atcoder.jp/contests/abc113/tasks/abc113_c

"""
import sys

from collections import defaultdict
from bisect import bisect_left

def solve(N, M, cities):
    res = defaultdict(list)
    for p, y in cities:
        res[p].append(y)
    for k in res.keys():
        res[k].sort()
    return ['{:06d}{:06d}'.format(p, bisect_left(res[p], y) + 1) for p, y in cities]


def main(args):
    N, M = map(int, input().split())
    cities = [[int(i) for i in input().split()] for i in range(M)]
    ans = solve(N, M, cities)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(m):
    a=list(map(int,input().split()))
    a.append(i)
    l.append(a)
l.sort(key=lambda x:x[1])
l.sort(key=lambda x:x[0])
j,y=0,1
for i in range(m):
    x=l[i].pop(0)
    y=y+1 if j==x else 1
    j=x
    l[i][0]=str(x).zfill(6)+str(y).zfill(6)
l.sort(key=lambda x:x[1])
for i in l:print(i[0])

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

ypi = []

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

ypi.sort()

rank = [0] * N

ans = [''] * M
for count in range(M):
    y, p, i = ypi[count]
    rank[p-1] += 1
    ans[i] = '{:06}'.format(p)+'{:06}'.format(rank[p-1])

for s in ans:
    print(s)

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

pre=[0]*n
citys=['']*m
for y,p,i in PY:
    pre[p-1]+=1
    citys[i]=str(p).zfill(6)+str(pre[p-1]).zfill(6)
for city in citys:
    print(city)

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

cs = {}
for p, y in PY:
	if not p in cs:
		cs[p] = [y]
	else:
		cs[p] += [y]

csm = {}
for k, v in cs.items():
	v.sort()
	csm[k] = {}
	for i, p in enumerate(v):
		csm[k][p] = i + 1

for p, y in PY:
	print("{:06d}{:06d}".format(p, csm[p][y]))

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


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

for i in range(M):
    pref_map[P[i]].append([i, Y[i]])


city_list = []
for k in pref_map.keys():
    pref_map[k].sort(key=lambda x: x[1])
    idx = 1
    for c in pref_map[k]:
        city_list.append([c[0], k, idx])
        idx += 1

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

for city in city_list:
    print(format(city[1], '06d') + format(city[2], '06d'))

Solution (Python):
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]
 
city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]
 
under6 = {}
for i,k in city.items():
    city[i] = sorted(k)
    for j in range(len(city[i])):
        under6[city[i][j]] = j + 1

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)
 
def change_birth_code(birth_num):
    return str(birth_num).zfill(6)
 
for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(under6[i[1]]))

Solution (Python):

from operator import itemgetter

N, M = list(map(int, input().split()))
A = [[0] * 4 for i in range(M)]
for i in range(M):
    A[i][0], A[i][1] = list(map(int, input().split()))
    A[i][2] = i

sorted_A = sorted(A, key=itemgetter(1))

P_num = [1]*N
for a in sorted_A:
    y = a[0]
    a[3] = P_num[y-1]
    P_num[y-1] += 1

B = sorted(sorted_A, key=itemgetter(2))
for b in B:
    print("%06d%06d" % (b[0], b[3]))

Solution (Python):
def mks(num):
  s=str(num)
  if len(s)<6:
    s='0'*(6-len(s))+s
  return s

n,m=map(int,input().split())
arr=[]
for i in range(m):
  p,y=map(int,input().split())
  arr.append([p,y,i])
ans=[0]*m
arr=sorted(arr,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
tmp=arr[0][0]
cnt=1
for i in range(m):
  if arr[i][0]==tmp:
    s1,s2=mks(tmp),mks(cnt)
    ans[arr[i][2]]=s1+s2
    cnt+=1
  else:
    cnt=1
    tmp=arr[i][0]
    s1,s2=mks(tmp),mks(cnt)
    ans[arr[i][2]]=s1+s2
    cnt+=1
for i in range(m):
  print(ans[i])

Solution (Python):
N,M = [ int(it) for it in input().split() ]
li = [ [i,[ int(it) for it in input().split() ]] for i in range(M) ]
li = [ (it[0],it[1][0],it[1][1]) for it in li]

sor = [ [] for i in range(N+1) ]
for i,p,y in li:
  sor[p].append((i,y))
[ it.sort(key = lambda x:x[1]) for it in sor]

coo = [0]*M
for so in sor:
  for j in range(len(so)):
    i,y = so[j]
    coo[i] = j+1
for i in range(M):
  print ( "{0:06d}{1:06d}".format(li[i][1], coo[i]) )

Solution (Python):
from operator import itemgetter
n,m=map(int,input().split())
l=[]
id_list=[]
for i in range(m):
  obj = list(map(int, input().split()))
  obj.append(i+1)
  l.append(obj)
l=sorted(l, key=itemgetter(0,1))
idx=0
for j in range(m):
  id_obj=[]
  if j == 0:
    idx=1
  else:

    if l[j][0] == l[j-1][0]:
      idx+=1
    else:
      idx =1
  id_obj.append(l[j][2])
  id_obj.append(str(l[j][0]).zfill(6)+str(idx).zfill(6))
  id_list.append(id_obj)
id_list = sorted(id_list)
for k in range(m):
  print(id_list[k][1])

Solution (Python):
N, M = map(int, input().split())
kv = {}
lst = []
for _ in range(M):
    x, y = map(int, input().split())
    lst.append("{0} {1}".format(x, y))
    if x in kv:
        kv[x][y] = 1
    else:
        kv[x] = {y:1}

for k1 in sorted(kv.keys()):
    keys = sorted(kv[k1].keys())
    for idx, k2 in enumerate(keys, 1):
        kv[k1][k2] = idx

for s in lst:
    x, y = map(int, s.split())
    print("{0:06d}{1:06d}".format(x,kv[x][y]))

Solution (Python):
from collections import namedtuple, defaultdict

City = namedtuple('City', ('num', 'pref', 'year'))
cities = defaultdict(list)

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

for _, cs in cities.items():
    cs.sort(key=lambda c: c.year)

ids = ['' for _ in range(m)]
for pref, cs in cities.items():
    for ith, c in enumerate(cs):
        ids[c.num] = str(c.pref).zfill(6) + str(ith + 1).zfill(6)

for id in ids:
    print(id)

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

N, M = [int(x) for x in input().split()]
P_Y_li = []
for _ in range(M):
    P_Y_li.append([_] + [int(x) for x in input().split()])

prev_P = 0
num_x_li = {}
for i in sorted(P_Y_li, key=lambda x:(x[1], x[2])):
    if prev_P != i[1]:
        
        prev_P = i[1]
        counter = 1
    num_x_li[i[0]] = counter
    counter += 1

for i in P_Y_li:
    print(str(i[1]).rjust(6,'0') + str(num_x_li[i[0]]).rjust(6,'0'))

Solution (Python):
from operator import itemgetter

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

s_PY = sorted(PY,key=itemgetter(1,2))

kenL = [0] * N
shiL = [''] * M

for i,p,y in s_PY:
    kenL[p-1] += 1
    shiL[i] = str(p).zfill(6) + str(kenL[p-1]).zfill(6)

for j in shiL:
    print(j)

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

ken = [0] * N
shis = [''] * M

for y, p, i in P:
    ken[p-1] += 1
    shis[i] = str(p).zfill(6) + str(ken[p-1]).zfill(6)
    
for shi in shis:
    print(shi)

Solution (Python):
N, M = map(int, input().split())
A = list(sorted([list(map(int, input().split())) + [i, 0] for i in range(M)]))
cur = 0
o = 1
for i, a in enumerate(A):
  if cur != a[0]:
    o = 1
    A[i][3] = o
    cur = a[0]
  else:
    o += 1
    A[i][3] = o

for a in sorted(A, key=lambda x: x[2]):
  print('{0:06d}{1:06d}'.format(a[0], a[3]))

Solution (Python):
N, M = map(int, input().split())
cities = [float("{}.{:010}".format(*tuple(map(int, input().split())))) for _ in range(M)]
sorted_cities = sorted(cities)

ids = {}
cnt = 1
before = -1
for c in sorted_cities:
    id_ = int(c)
    if before != id_:
        before = id_
        cnt = 1
    else:
        cnt += 1
    ids[c] = cnt

[print("{:06}{:06}".format(int(c), ids[c])) for c in cities]

Solution (Python):
N, M = map(int, input().split())
cities = [int("{}{:010}".format(*tuple(map(int, input().split())))) for _ in range(M)]
sorted_cities = sorted(cities)

ids = {}
cnt = 1
before = -1
for c in sorted_cities:
    id_ = c//10000000000
    if before != id_:
        before = id_
        cnt = 1
    else:
        cnt += 1
    ids[c] = cnt

[print("{:06}{:06}".format(c//10000000000, ids[c])) for c in cities]

Solution (Python):
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
PYs = [list(map(int, stdin.readline().rstrip().split()))+[i] for i in range(M)]
PYs.sort(key=lambda x:x[1])

num = [0]*N
ans = [""]*M

for p, y, i in PYs:
    num[p-1]+=1
    ans[i] = str(p).zfill(6) + str(num[p-1]).zfill(6)

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

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits



def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))

def update(bit,i, dp):
    bit[i] = dp
    return bit

def query(bit, i):
    lis = [bit[j] for j in range(i)]
    return max(lis)


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

n,m=MAP()

py = [LIST() for _ in range(m)]
py = [[i,x[0],x[1]] for i,x in enumerate(py)]
lis=py.copy()
lis.sort(key=lambda x: (x[1], x[2]))

ans = [""] * m

tmp=1
ct = 1

for x in lis:
    if tmp!=x[1]:
        tmp = x[1]
        ct = 1
    ans[x[0]] = '{:06}{:06}'.format(x[1], ct)
    ct += 1
        
for x in ans:
    print(x)

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits



def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))

def update(bit,i, dp):
    bit[i] = dp
    return bit

def query(bit, i):
    lis = [bit[j] for j in range(i)]
    return max(lis)


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

n,m=MAP()

py = [LIST() for _ in range(m)]
py = [[i,x[0],x[1]] for i,x in enumerate(py)]
lis=deepcopy(py)
lis.sort(key=lambda x: (x[1], x[2]))

ans = [""] * m

tmp=1
ct = 1

for x in lis:
    if tmp!=x[1]:
        tmp = x[1]
        ct = 1
    ans[x[0]] = '{:06}{:06}'.format(x[1], ct)
    ct += 1
        
for x in ans:
    print(x)

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

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

p_to_c_list = {}
for i in range(M):
    if p_to_c_list.get(PY[i][0]) == None:
        p_to_c_list[(PY[i][0])] = {'count': 1, 'city': {PY[i][1]: 1}}
    else:
        p_to_c_list[(PY[i][0])]['count'] += 1
        current_i = p_to_c_list[(PY[i][0])]['count']
        p_to_c_list[(PY[i][0])]['city'][PY[i][1]] = current_i

for py in PY_org:
    print('{:06}{:06}'.format(py[0], p_to_c_list[py[0]]['city'][py[1]]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
PY = [LIST() for _ in range(M)]
PY_ = deepcopy(PY)
PY_.sort(key=lambda x: (x[0], x[1]))

tmp = 0
i = 0
lis = []
dic = {}
for p, y in PY_:
	if p == tmp:
		i += 1
	else: 
		lis.append([])
		tmp = p
		i = 1
	dic[str(p)+"_"+str(y)]=str(p).zfill(6)+str(i).zfill(6)

for p, y in PY:
	print(dic[str(p)+"_"+str(y)])

Solution (Python):
N,M = map(int,input().split())
citys = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    citys[i].append(i)
citys.sort()
ppref = 0
city_code = 0
for city in citys:
    if ppref == city[0]:
        city_code += 1
    else:
        ppref = city[0]
        city_code = 1
    str_pref = str(city[0]).zfill(6)
    str_city = str(city_code).zfill(6)
    city.append(str_pref+str_city)

for city in sorted(citys, key=lambda x:x[2]):
    print(city[3])

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

N,M = map(int, input().split())
P = [0]*M
Y = [0]*M
for i in range(M):
	P[i],Y[i] = map(int, input().split())
 
p_dict = {} 
for i in range(M):
	p_dict.setdefault(P[i],[]).append(Y[i])


under6 = {} 
for p in p_dict.keys():
  sorted_year = sorted(p_dict[p])
  for i in range(len(sorted_year)):
    under6[sorted_year[i]] = i + 1

for i in range(M):
  print(str(P[i]).zfill(6) + str(under6[Y[i]]).zfill(6))

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

p_dict = {}
for i in range(M):
  p_dict.setdefault(P[i],[]).append(Y[i])
under6 = {}
for p in p_dict.keys():
  sorted_year = sorted(p_dict[p])
  for i in range(len(sorted_year)):
    under6[sorted_year[i]] = i + 1

for i in range(M):
  print(str(P[i]).zfill(6) + str(under6[Y[i]]).zfill(6))

Solution (Python):
n, m = map(int, input().split())
dp = [[] for i in range(n)]
for i in range(m):
    p, y = map(int, input().split())
    dp[p - 1].append([i, y])
for i, p in enumerate(dp):
    p = sorted(p, key=lambda x : x[1])
    dp[i] = p
ans = []
for i, p in enumerate(dp):
    for j, a in enumerate(p):
        s = '{:06}'.format(i + 1) + '{:06}'.format(j + 1)
        ans.append([a[0], s])
ans = sorted(ans)
for i, s in ans:
    print(s)

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

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

LL = sorted(L)
num = []

for i in range(len(LL)):
    if i == 0:
        cnt = 1
    else:
        if (LL[i][0] == LL[i-1][0]):
            cnt += 1
        else:
            cnt = 1
    id.append(LL[i][2])
    num.append(str(LL[i][0]).zfill(6) + str(cnt).zfill(6))

numnum = [x for _ , x in sorted(zip(id,num))]

for x in numnum:
    print(x)

Solution (Python):
n,m=map(int,input().split())
P=[]
for i in range(m):
    p,y=map(int, input().split())
    P.append([p,y,i])
nums=[0]*n
ans=[""]*m
P.sort(key=lambda x:x[1])

for p,y,i in P:
    nums[p-1]+=1
    ans[i]=(6-len(str(p)))*"0"+str(p)+(6-len(str(nums[p-1])))*"0"+str(nums[p-1])
for an in ans:
    print(an)

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

def main():
    ps = [[] for _ in range(N)]

    for m in range(M):
        p, y = [int(n) for n in input().split()]
        pref = ps[p - 1]
        pref.append([m, y])

    result = []

    for i, pref in enumerate(ps):
        pref.sort(key=lambda p: p[1])
        for j, p in enumerate(pref):
            result.append([p[0], '{:06}{:06}'.format(i + 1, j + 1)])

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

    ans = '\n'.join(map(lambda p: p[1], result))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
li = [inpl()+[i] for i in range(M)]
li = sorted(li, key=lambda x: x[1])
ans = [0]*M
cnts = defaultdict(int)
for i in range(M):
    p,y,ind = li[i]
    s1 = str(p).zfill(6)
    s2 = str(cnts[p]+1).zfill(6)
    cnts[p] += 1
    ans[ind] = s1+s2

for a in ans:
    print(a)

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

for i in range(M) : 
    tmp = []
    tmp = list(map(int, input().split()))
    tmp.append(i)
    L.append(tmp)
    
LL = sorted(L)
num = []

for i in range(len(LL)) : 
    if i == 0 : 
        cnt = 1

    else : 
        if(LL[i][0] == LL[i-1][0]) : 
            cnt += 1
        else : 
            cnt = 1
        
    id.append(LL[i][2])
    num.append(str(LL[i][0]).zfill(6) + str(cnt).zfill(6))

numnum = [x for _,x in sorted(zip(id, num))] 

for x in numnum : 
    print(x)

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

for i in range(M) : 
    tmp = []
    tmp = list(map(int, input().split()))
    tmp.append(i)
    L.append(tmp)
    
LL = sorted(L)
num = []

for i in range(len(LL)) : 
    if i == 0 : 
        cnt = 1

    else : 
        if(LL[i][0] == LL[i-1][0]) : 
            cnt += 1
        else : 
            cnt = 1
        
    id.append(LL[i][2])
    num.append(str(LL[i][0]).zfill(6) + str(cnt).zfill(6))

numnum = [x for _ , x in sorted(zip(id, num))]

for x in numnum : 
    print(x)

Solution (Python):
n,m = map(int,input().split())
P = [list(map(int,input().split()))+[0,i] for i in range(m)]
P.sort(key = lambda x:x[1])
city = {}
for p in P:
    if p[0] in city:
        city[p[0]] += 1
    else:
        city[p[0]] = 1
    p[2] = city[p[0]]
P.sort(key = lambda x:x[3])
for p in P:
    print(str(p[0]).zfill(6)+str(p[2]).zfill(6))

Solution (Python):
N,M=[int(a) for a in input().split(" ")]
PY = [[int(a) for a in input().split(" ")] for i in range(M)]
from collections import defaultdict
dic = defaultdict(list)
for i, (p, y) in enumerate(PY):
    dic[p].append((i, y))
ans = []
fill6 = lambda s:(6-len(s))*"0"+s
for p, arr in dic.items():
    s = fill6(str(p))
    arr = sorted(arr, key=lambda t: t[1])
    ans += [(j, s+fill6(str(i+1))) for i, (j, _) in enumerate(arr)]
for j, idx in sorted(ans, key=lambda t:t[0]):
    print(idx)

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

lst = []
for i in range(M):
    a = list(map(int, input().split()))
    a += [i] 
    lst += [a]

lst.sort()


ken = -1
x = 0
ans = []
for j in range(M):
    if ken != lst[j][0]: 
        x = 1 
        ken = lst[j][0]

        
    else: 
        x += 1
        

    ans += [[lst[j][2], ken, x]]

ans.sort()

for k in range(M):
    P = '{:0>6}'.format(ans[k][1])
    X = '{:0>6}'.format(ans[k][2])
    print (P+X)

Solution (Python):
import sys
from collections import defaultdict
from copy import deepcopy

input = sys.stdin.readline
N, M = list(map(int, input().split()))

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

sorted_PY = deepcopy(PY)
sorted_PY.sort(key=lambda x: x[1])

p_count_dict = defaultdict(lambda: 0)
y_dict = {}

for py in sorted_PY:
    p_count_dict[py[0]] += 1
    y_dict[py[1]] = p_count_dict[py[0]]

for py in PY:
    
    print('{}{}'.format(str(py[0]).zfill(6), str(y_dict[py[1]]).zfill(6)))

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

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

nums = [0] * N
ans = [''] * M
pys.sort(key=lambda x:x[1])

for p, y, i in pys:
    nums[p-1] += 1
    ans[i] = str(p).zfill(6) + str(nums[p-1]).zfill(6)

for an in ans:
    print(an)

Solution (Python):
import heapq

N, M = [int(i) for i in input().split()]
heaps = [[] for _ in range(N + 1)]
cities = [None] * (M+1)
for m in range(M):
    p, y = [int(i) for i in input().split()]
    heapq.heappush(heaps[p], (y, p, m))

for heap in heaps:
    id = 0
    while len(heap) > 0:
        id += 1
        y, p, m = heapq.heappop(heap)
        cities[m] = "{:06d}{:06d}".format(p, id)

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

Solution (Python):
N, M = map(int,input().split())
L = []
for i in range(M):
    p, y = map(int,input().split())
    L.append((p,y,i))
PY = sorted(L)
from collections import defaultdict
d = defaultdict(int)
ID = [None]*M
for p,y,i in PY:
    d[p] += 1
    ID[i] = d[p]
for i in range(M):
    p,y,j = L[i]
    print("{:06}{:06}".format(p, ID[i]))

Solution (Python):
N, M = list(map(int, input().split()))
temp = [list(map(int, input().split())) for i in range(M)]
temp = list(zip(*temp))
P, Y = temp

data = dict()
for p, y in zip(P, Y):
  if p not in data:
    data[p] = [y]
  else:
    data[p].append(y)

data = {i:{value:j+1 for j, value in enumerate(sorted(data[i]))} for i in data.keys()}

for p, y in zip(P, Y):
  print("{:06}{:06}".format(p, data[p][y]))

Solution (Python):




from collections import Counter

N, M = map(int, input().split())
PY = [ (i, P, Y) for i, (P, Y) in enumerate([map(int, input().split()) for _ in range(M)])]

answers = [0 for x in range(M)]
counter = Counter()

for index, P, Y in sorted(PY, key = lambda x : x[2]):
    counter[P] += 1
    answers[index] = "{:06}{:06}".format(P, counter[P])

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

Solution (Python):


from itertools import chain
from collections import Counter

N,M = map(int, input().split())
PY = [ (i, P, Y) for i, (P, Y) in enumerate([map(int, input().split()) for _ in range(M)])]

answers = [0 for x in range(M)]
counter = Counter()

for index, P, Y in sorted(PY, key = lambda x : x[2]):
    counter[P] += 1
    answers[index] = "{:06}{:06}".format(P, counter[P])

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

Solution (Python):


from itertools import chain
from collections import Counter

N,M = map(int, input().split())
PY = [ (i, P, Y) for i, (P, Y) in enumerate([tuple(map(int, input().split())) for _ in range(M)])]

answers = [0 for x in range(M)]
counter = Counter()

for index, P, Y in sorted(PY, key = lambda x : x[2]):
    counter[P] += 1
    answers[index] = "{:06}{:06}".format(P, counter[P])

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

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

d = {}
for i in range(M):
    p,y = map(int,input().split())
    if p in d.keys():
        d[p].append([p,y,i])
    else:
        d[p] = [[p,y,i]]

ans = []
for k in d.keys():
    d[k] = sorted(d[k],key=lambda x:x[1])
    for i,d_ in enumerate(d[k]):
        d_.append(i+1)
    ans += d[k]

ans = sorted(ans,key=lambda x:x[2])
for a in ans:
    print(str(a[0]).zfill(6)+str(a[3]).zfill(6))

Solution (Python):
import math
N,M = list(map(int,input().split(" ")))
towns = {}
ans = [0] * M
for i in range(M):
    temp = list(map(int,input().split(" ")))
    num = temp[0]
    year = temp[1]
    if num not in towns:
        towns[num] = [(year,i)]
    else:
        towns[num].append((year,i))


for k,v in towns.items():
    
    i1 = str(k).zfill(6)
    v_sorted = sorted(v,key = lambda x:x[0])
    
    for i,town in enumerate(v_sorted):
        
        i2 = str(i+1).zfill(6)
        
        ind = town[1]
        ans[ind] = i1 + i2

for a in ans:
    print(a)

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

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

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

for v in l:
    ll[v[0] - 1].append(v[1])
    
for i in range(len(ll)):
    ll[i].sort()
    
for v in l:
    index = bisect.bisect_right(ll[v[0] - 1], v[1])
    print("{:0=6}{:0=6}".format(v[0], index))

Solution (Python):
n,m=map(int,input().split())
city={}
year=[]
for i in range(m):
    p,y=map(int,input().split())
    city[y]=p
    year.append(y)
city=sorted(city.items())
answer={}
count=[]
for i in range(n):
    count.append(1)
for i in city:
    f=str(i[1]).zfill(6)
    l=str(count[i[1]-1]).zfill(6)
    count[i[1]-1]=count[i[1]-1]+1
    answer[i[0]]=f+l
for i in year:
    print(answer[i])

Solution (Python):
import sys
from collections import defaultdict
from operator import itemgetter

input = sys.stdin.readline

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

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

ans = [None] * M
for k, v in A.items():
    v.sort(key=itemgetter(0))
    for i in range(len(v)):
        _, j = v[i]
        c1 = str(k).zfill(6)
        c2 = str(i + 1).zfill(6)
        ans[j] = c1 + c2
print('\n'.join(ans))

Solution (Python):

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

PM_list = [ input() for _ in range(M) ]
PM_list = [ list(map(int,_.split(" "))) for _ in PM_list]
PM_dict = {}

for i in PM_list:
    if i[0] in PM_dict:
        PM_dict[i[0]].append(i[1])
    else:
        PM_dict[i[0]] = [i[1]]

for j in PM_dict:
    PM_dict[j].sort()

for k in PM_list:
    print("{}{}".format(str(k[0]).zfill(6),str(bisect.bisect_left(PM_dict[k[0]],k[1])+1).zfill(6)))

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