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):
nm=list(map(int,input().split()))
p=[]
for i in range(nm[0]):
    p.append([])
for i in range(nm[1]):
    py=list(map(int,input().split()))
    p[py[0]-1].append([i,py[1]])


from operator import itemgetter
for i in range(nm[0]):
    p[i].sort(key=itemgetter(1))
    
    for j in range(len(p[i])):
        p[i][j][-1]=j+1
        p[i][j].append(i+1)


c=p[0]
for i in range(1,nm[0]):
    c+=p[i]
c.sort()
for i in range(nm[1]):
    prefecture=str(c[i][2])
    rank=str(c[i][1])
    padding_p="0"*(6-len(prefecture))
    padding_r="0"*(6-len(rank))
    print(padding_p+prefecture+padding_r+rank)

Solution (Python):
import bisect
from collections import defaultdict
n,m = map(int,input().split())
p = [list(map(int, input().split())) for _ in range(m)]
 
a = defaultdict(list)
for x,y in sorted(p):
    a[x].append(y)
for x,y in p:
    
    z=bisect.bisect(a[x],y)
    print("{0:06d}{1:06d}".format(x,z))

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

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

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

X=[0]*M
for i,d in enumerate(A):
  d.sort()
  for k,(y,j) in enumerate(d):
    X[j]=str(i+1).zfill(6)+str(k+1).zfill(6)
print(*X,sep='\n')

Solution (Python):
n,m=map(int,input().split())
L=[]
for i in range(m):
    l=[i]+list(map(int,input().split()))+[0]
    L.append(l)
LS=sorted(L,key=lambda x:(x[1],x[2]))
LS[0][3]=1
for i in range(m-1):
    if LS[i][1]==LS[i+1][1]:
        LS[i+1][3]=LS[i][3]+1
    else:
        LS[i+1][3]=1
LR=sorted(L,key=lambda x:x[0])
for a,b,c,d in LR:
    print(str(b).zfill(6)+str(d).zfill(6))

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

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

ans=[None]*M
for j,py in enumerate(PY): 
    py.sort()
    for k,(y,i) in enumerate(py):
        ans[i]=str(j+1).zfill(6) + str(k+1).zfill(6)

print(*ans,sep="\n")

Solution (Python):
import sys
from collections import defaultdict

n, m, *py = map(int, sys.stdin.read().split())
py = list(zip(*[iter(py)] * 2))

def main():
    ids = defaultdict(list)
    for p, y in py:
        ids[p].append(y)
    
    for p, ys in ids.items():
        ids[p] = dict([(y, i) for i, y in enumerate(sorted(ys), 1)])
    
    for p, y in py:
        x = ids[p][y]
        first = str(p)
        last = str(x)
        first = '0' * (6 - len(first)) + first
        last = '0' * (6 - len(last)) + last
        yield first + last
    
if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

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


def main():
    N, M = [int(x) for x in input().split()]
    PY = []
    for i in range(M):
        PY.append([int(x) for x in input().split()] + [i])


    PY_sorted = sorted(PY, key=itemgetter(0, 1))

    ans = [""] * M
    prev = 0
    yid = 0
    for i, v in enumerate(PY_sorted):
        if prev == 0 or prev == v[0]:
            yid += 1
        else:
            yid = 1
        prev = v[0]
        ans[v[2]] += str(v[0]).zfill(6) + str(yid).zfill(6)


    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):
t=input()
N=int(t.split()[0])
M=int(t.split()[1])

city=[0]*M
for i in range(M):
  te=[int(x) for x in input().split()]
  city[i]={'i':i+1,'p':int(te[0]),'y':int(te[1])}

city_sorted = sorted(city,key = lambda x: (x['p'], x['y']))

x=0
temp_p=city_sorted[0]['p']
for c in city_sorted:
  if temp_p == c['p']:
    x+=1
  else:
    temp_p=c['p']
    x=1
  c['id']="{0:06d}{1:06d}".format(c['p'],x)
  
for ci in city:
  print(ci['id'])

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

li = [[] for i in range(n)]
memo = [0 for i in range(m)]

def search(p,y):
    fst = 0
    lst = len(li[p])-1

    while(fst <= lst):
        mid = (fst+lst)//2
        if li[p][mid] == y:
            return mid

        elif li[p][mid] < y:
            fst = mid+1
        
        elif li[p][mid] > y:
            lst = mid-1


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

for i in range(n):
    li[i].sort()

for i in range(m):
    a = memo[i][0]+1
    b = search(memo[i][0],memo[i][1])
    print("{:0>6}".format(a),end ="")
    print("{:0>6}".format(b+1))

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())
PY = sorted(((i, tuple(map(int, input().split()))) for i in range(M)), key=itemgetter(1))
L = []
prev, x = 0, 1
for i, (p, _y) in PY:
    if p == prev:
        x += 1
    else:
        prev = p
        x = 1
    L.append((i, "{:06d}{:06d}".format(p, x)))
L.sort()
print(*[l for _, l in L], sep="\n")

Solution (Python):
from collections import defaultdict

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

prefectures = defaultdict(list)
for idx, (p, y) in enumerate(data):
    prefectures[p].append([idx, y, None])


for pref in prefectures:
    prefectures[pref].sort(key=lambda r: r[1])
    rows = prefectures[pref]
    for x, row in enumerate(rows):
        id = "{:06d}{:06d}".format(pref, x + 1)
        row[2] = id

all_list = []
for pref in prefectures.values():
    all_list.extend(pref)

all_list = sorted(all_list, key=lambda r: r[0])


for r in all_list:
    print(r[2])

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    py = [list(map(int, readline().split())) for _ in range(m)]
    for i in range(m):
        py[i].append(i)
    py.sort()
    d = collections.defaultdict(int)
    for i in range(m):
        d[py[i][0]] += 1
        py[i].append(d[py[i][0]])
    py.sort(key=lambda x: x[2])
    for i in range(m):
        print("".join((["0"] * 6 + list(str(py[i][0])))[-6:] + (["0"] * 6 + list(str(py[i][-1])))[-6:]))


if __name__ == '__main__':
    solve()

Solution (Python):
n, m = map(int, input().split())
Py = []
for i in range(m):
    py = list(map(int, input().split()))
    Py.append(py+[i])
Py = sorted(sorted(Py, key = lambda x: x[1]))
tmp = -1
ans = []
for i in range(m):
    out = str(Py[i][0]).zfill(6)
    cnt = cnt + 1 if Py[i][0] == tmp else 1
    out += str(cnt).zfill(6)
    tmp = Py[i][0]
    ans.append([Py[i][2], out])
ans.sort()
for i in range(m):
    print(ans[i][1])

Solution (Python):
n, m = map(int, input().split())
Py = []
for i in range(m):
    py = list(map(int, input().split()))
    Py.append(py+[i])
Py = sorted(sorted(Py, key = lambda x: x[1]))
tmp = -1
ans = []
for i in range(m):
    out = str(Py[i][0]).zfill(6)
    cnt = cnt + 1 if Py[i][0] == tmp else 1
    out += str(cnt).zfill(6)
    tmp = Py[i][0]
    ans.append([Py[i][2], out])
ans.sort()
for i in range(m):
    print(ans[i][1])

Solution (Python):
from collections import defaultdict

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






ans = [0]*m

p_yi_table = [[] for i in range(n+1)]
for i,(p,y) in enumerate(py):
    p_yi_table[p].append((y,i))
for p, yi_list_by_p in enumerate(p_yi_table):
    yi_list_by_p.sort()
    for j,(y,i) in enumerate(yi_list_by_p):
        s = str(p).zfill(6) + str(j+1).zfill(6)
        ans[i] = s

print(*ans, sep='\n')

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

def main():
    N,M = map(int,input().split())
    f = []
    for i in range(M):
        P,Y = map(int,input().split())
        f.append([P,Y,i])
        
    f.sort(key = itemgetter(0,1))
    s = 1
    count = 0
    for i in range(M):
        if s != f[i][0]:
            s = f[i][0]
            count = 1
            f[i][1] = count
        else:
            count += 1
            f[i][1] = count
            
    ans = []
    for i in range(M):
        p,y,num = f[i]
        lp,ly = len(str(p)),len(str(y))
        ad = "0"*(6-lp) + str(p) + "0"*(6-ly) + str(y)
        ans.append((num,ad))
        
    ans.sort(key = itemgetter(0))
    for i in range(M):print(ans[i][1])
    
if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
x = []
for _ in range(m):
    a, b = map(int, input().split())
    x.append([a, b, 0])
y = sorted(x)
y[0][2] = 1
cnt = 1
for i in range(1, m):
    if y[i][0] == y[i - 1][0]:
        cnt += 1
        y[i][2] = cnt
    else:
        cnt = 1
        y[i][2] = cnt
for i in range(m):
    print((6 - len(str(x[i][0]))) * '0', end='')
    print(str(x[i][0]), end='')
    print((6 - len(str(x[i][2]))) * '0', end='')
    print(str(x[i][2]))

Solution (Python):
from collections import defaultdict


def solve():
    N, M = map(int, input().split())
    p_dict = defaultdict(list)
    P = [0] * M
    Y = [0] * M
    for i in range(M):
        p, y = map(int, input().split())
        p_dict[p].append(y)
        P[i], Y[i] = p, y
    
    recog_num = defaultdict(int)
    for i in range(1, N+1):
        birth = sorted(p_dict[i])
        for index, y in enumerate(birth):
            recog_num[y] = index + 1
    
    for i in range(M):
        print('{:06d}'.format(P[i]) + '{:06d}'.format(recog_num[Y[i]]))


if __name__ == '__main__':
    solve()

Solution (Python):
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
PY = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

counts = defaultdict(int)

PY = np.array(PY, dtype=int)
idx = PY[:, 1].argsort()
ans = [''] * M
for i in idx:
    p, y = PY[i]
    counts[p] += 1
    ans[i] = '{:06d}{:06d}'.format(p, counts[p])
if ans:
    print(*ans, sep='\n')

Solution (Python):
import collections
import itertools


City = collections.namedtuple("City", ("number", "pref", "year"))

n, m = [int(i) for i in input().split()]
cities = []
for i in range(m):
    pref, year = input().split()
    city = City(i, int(pref), int(year))
    cities.append(city)
id_numbers = []
cities.sort(key=lambda x: x.year)
cities.sort(key=lambda x: x.pref)
ans = []
groups = itertools.groupby(cities, key=lambda x: x.pref)
for g in groups:
    for i, d in enumerate(sorted(g[1], key=lambda x: x.year)):
        ans.append((d.number, d.pref, i+1))
ans.sort(key=lambda x: x[0])
for a in ans:
    print("{:0>6}{:0>6}".format(a[1], a[2]))

Solution (Python):
import collections
City = collections.namedtuple("City", ("number", "pref", "year"))

n, m = [int(i) for i in input().split()]
cities = []
for i in range(m):
    pref, year = input().split()
    city = City(i, int(pref), int(year))
    cities.append(city)
id_numbers = []
cities.sort(key=lambda x: x.year)
cities.sort(key=lambda x: x.pref)
prev_pref = None
for city in cities:
    if prev_pref is None or city.pref != prev_pref:
        rank = 1
    else:
        rank += 1
    id_numbers.append((city.number, city.pref, rank))
    prev_pref = city.pref
id_numbers.sort(key=lambda x: x[0])
for i in id_numbers:
    print("{:0>6}{:0>6}".format(i[1], i[2]))

Solution (Python):
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
import sys
input = sys.stdin.readline

N,M = two_int()

inputs =[]

dicts={}

for i in range(M):
    P,S = input().split()
    S=int(S)
    inputs.append([P,S])
    
    if P not in dicts:
        dicts[P]=[]
    
    dicts[P].append(S)
    



pref_strs={}
for k, v in dicts.items():
    dicts[k]=sorted(dicts[k])
    pref_strs[k]=k.zfill(6)

import bisect

for i in inputs:
    P,S=i
    
    city_index = bisect.bisect_right(dicts[P], S)
    city_str=str(city_index)
    
    print(pref_strs[P]+city_str.zfill(6))

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

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

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

ans = [0] * M
for k,vs in dic.items():
    order = 1
    for city,year in vs:
        ans[city] = (k,order)
        order += 1

for city, order in ans:
    print('{:06d}{:06d}'.format(city,order))

Solution (Python):
def main():
    N, M, *PY = map(int, open(0).read().split())
    lst = []
    ans = [""] * M
    for k, py in enumerate(zip(*[iter(PY)] * 2)):
        lst.append((py[0], py[1], k))
    lst.sort()
    pre, num = lst[0][0], 1
    for cur, y, i in lst:
        if pre != cur:
            num = 1
        ans[i] = "{:06}{:06}".format(cur, num)
        num += 1
        pre = cur
    print("\n".join(ans))
    return


main()

Solution (Python):

import bisect

N, M = map(int, input().split())
cities = []
prefectures = [[] for _ in range(N+1)]

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

for (y, p) in sorted(cities, key=lambda x: x[0]):
  prefectures[p].append(y)

for (y, p) in cities:
  x = bisect.bisect_right(prefectures[p], y) 
  pid = "00000" + str(p)
  xid = "00000" + str(x)
  print(pid[::-1][:6][::-1] + xid[::-1][:6][::-1])

Solution (Python):
n,m = map(int,input().split())
l = []
for i in range(m):
    p,y = map(int,input().split())
    l.append([i,p,y])
count = [1 for i in range(n)]
l.sort(key=lambda x: x[2])
for i in l:
    pp = i[1]
    i.append(count[pp - 1])
    count[pp - 1] += 1
l.sort()
for i in l:
    x = i[1]
    x_zero = str(x).zfill(6)
    y = i[3]
    y_zero = str(y).zfill(6)
    print(x_zero+y_zero)

Solution (Python):
N, M = map(int, input().split())
temp = [list(map(int, input().split())) for i in range(M)]
cities = []
for x, city in enumerate(temp):
    cities.append([x+1, city[0], city[1]])





prefectures = [[] for i in range(N)]
for city in cities:
    prefectures[city[1]-1].append(city)



ID_list = []

for prefecture in prefectures:
    prefecture.sort(key=lambda x:x[2])
    
    
    
    for x, city in enumerate(prefecture):
        ID_list.append([city[0], city[1], x+1])

ID_list.sort()





for ID in ID_list:
    temp = '{0:06d}'.format(ID[1])
    temp = temp + '{0:06d}'.format(ID[2])
    print(temp)

Solution (Python):
import bisect

n, m = map(int, input().split())
cities = [[] for _ in range(n)]
ans = [None] * m
idxMap = {}

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

    
    

for i in range(n):
    cities[i].sort()



for i in range(n):
    for j in range(len(cities[i])):
        year = cities[i][j]
        idx = idxMap[year]
        ans[idx] = str(i+1).zfill(6) + str(j+1).zfill(6)


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

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

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

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

    for i in range(m):
        print(str(PY[i][0]).rjust(6,'0')+str(PY[i][3]).rjust(6,'0'))


if __name__ == '__main__':
    main()

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

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

for i in range(m):
    if  pref != lstpy[i][0]:
        pref = lstpy[i][0]
        cnt = 1
    else:
        cnt += 1
    num = "0"*(6-len(str(pref)))+str(pref)+"0"*(6-len(str(cnt)))+str(cnt)
    lstpy[i].append(num)

lstpy.sort(key=lambda x:x[2])
for i in range(m):
    print(lstpy[i][3])

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

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

ken=""
for i in range(m):
    if ken != l[i][0]:
        x = 1
        ken = l[i][0]
    else:
        x += 1
    l[i].append(str(ken).zfill(6)+str(x).zfill(6))

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

for i in range(m):
  print(l[i][3])

Solution (Python):
n,m = map(int,input().split())
s = []
for i in range(m):
    a =list(map(int,input().split()))
    a.append(i)
    s.append(a)
s.sort()
ans = [0 for i in range(m)]
num = 0
ans_ = ""
for i in range(m):
    if num != s[i][0]:
        num = s[i][0]
        count = 1
    ans_ = str(s[i][0])
    ans__ = str(count)
    for j in range(5):
        if len(ans_) < 6:
            ans_ = "0"+ans_
        if len(ans__) < 6:
            ans__ = "0" + ans__
    ans[s[i][2]] = ans_+ans__
    count += 1
for i in range(m):
    print(ans[i])

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


def main():
    n, m = map(int, input().split())
    ans_id = [None]*m
    p_count = [0]*(n+1)

    list_ipy = [None]*m
    for i in range(m):
        p, y = map(int, input().split())
        list_ipy[i] = (i, p, y)
    list_ipy.sort(key=lambda x: x[2])

    for ipy in list_ipy:
        i, p, _ = ipy
        p_count[p] += 1
        first = format(p, '06')
        second = format(p_count[p], '06')
        ans_id[i] = first + second

    for id in ans_id:
        print(id)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools
import numpy
input = sys.stdin.readline
N,M = [int(i) for i in input().split()]
nes = [0] * M
for i in range(M) :
    lis = [int(i) for i in input().split()]
    lis.append(i+1)
    nes[i] = lis
nes.sort()
answer_sheet = ['0'] * M
count = 0
for i in range(M) :
    if i < M - 1 :
        if nes[i][0] == nes[i+1][0] :
            count+=1
            pre = str(nes[i][0]).rjust(6,'0')
            new = str(count).rjust(6,'0')
            answer_sheet[nes[i][2] - 1] = pre + new
        else :
            count+=1
            pre = str(nes[i][0]).rjust(6,'0')
            new = str(count).rjust(6,'0')
            answer_sheet[nes[i][2] - 1] = pre + new
            count = 0
    else :
        count+=1
        pre = str(nes[i][0]).rjust(6,'0')
        new = str(count).rjust(6,'0')
        answer_sheet[nes[i][2] - 1] = pre + new
for i in range(M) :
    print(answer_sheet[i])

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


def ume0(num):
    return "0" * (6 - len(str(num))) + str(num)


now_city = -1
simo = 0
ans = {}
for P, Y in sorted(PYlist):
    if P != now_city:
        now_city = P
        simo = 0
    simo += 1
    ans[(P, Y)] = ume0(now_city) + ume0(simo)

for PY in PYlist:
    print(ans[PY])

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

D.sort(key=lambda x:x[2])
for i in range(M):
  P = D[i][1]
  R = C[P] + 1
  C[P] = R
  st = '{0:06d}'.format(P)
  st = st + '{0:06d}'.format(R)
  D[i] = [D[i][0],st]
D.sort(key=lambda x:x[0])
for i in range(M):
  print(D[i][1])

Solution (Python):
N,M=map(int,input().split())
C = [0]*(N+1)
D = []
for i in range(M):
  P,Y=map(int,input().split())
  D.append([i,P,Y])
D.sort(key=lambda x:x[2])
for i in range(M):
  P = D[i][1]
  R = C[P] + 1
  C[P] = R
  st = '{0:06d}'.format(P)
  st = st + '{0:06d}'.format(R)
  D[i] = [D[i][0],st]
D.sort(key=lambda x:x[0])
for i in range(M):
  print(D[i][1])

Solution (Python):

import sys


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    hashTable = {}

    for i in range(M):
        if hashTable.get(P[i]) == None:
            hashTable[P[i]] = [Y[i]]
        else:
            hashTable[P[i]].append(Y[i])
    
    
    answerTable = {}

    for key,value in hashTable.items():
        value.sort()
        
        for i,v in enumerate(value):
            answerTable[v] = str(key).zfill(6) + str(i+1).zfill(6)
    
    for i in range(M):
        print(answerTable[Y[i]])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    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 = map(int, input().split())
cy = [1] * N
city = []

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

ans = [""] * M

for y, p, i in city:
  ans[i] = ("000000" + str(p))[-6:] + ("000000" + str(cy[p-1]))[-6:]
  cy[p-1] += 1

print(*ans, sep="\n")

Solution (Python):
n, m = list(map(int,(input().split())))
l = []
d = {}
for _ in range(m):
  x = list(map(int,(input().split())))
  l.append(x)


l2 = sorted(l)



count = 1
pcount = 1
p = 0
d = {}
for i in l2:

  if p != i[0] :
    pcount = 1
    p = i[0]
  else :
    pcount += 1 
    p = i[0]
  d[str(i)] = str(i[0]).zfill(6)+ str(pcount).zfill(6)

for i in l:
  print(d[str(i)])

Solution (Python):
def examA():
    X, Y = LI()
    ans = X + Y//2
    print(ans)
    return

def examB():
    N = I()
    T, A = LI()
    H = LI()
    cur = 10**9; ans = 0
    for i in range(N):
        now = abs(A - (T - H[i]*0.006))
        if cur>now:
            cur = now
            ans = i
    print(ans+1)
    return

def examC():
    N, M = LI()
    PY = [[]for _ in range(M)]
    d = defaultdict(int)
    ans = [[]for _ in range(M)]
    for i in range(M):
        PY[i] = LI()
        PY[i].append(i)
    PY.sort(key=lambda x:x[1])
    for p,y,s in PY:
        d[p] +=1
        cur = str(p).zfill(6) + str(d[p]).zfill(6)
        ans[s] = cur
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

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

spy = sorted(py)

signate = {}
cnt = 0
last_p = 0
for p, y in spy:
    pref = "{:06}".format(p)
    if last_p == p:
        cnt += 1
    else:
        last_p = p
        cnt = 1
    year = "{:06}".format(cnt)
    signate["{}-{}".format(p, y)] = pref+year

for p, y in py:
    print(signate['{}-{}'.format(p, y)])

Solution (Python):
N, M = map(int,input().split())
PYP = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    PYP[i].append(i)
PY = sorted(PYP)
P = PY[0][0]
S = 0
for i in range(M):
    if PY[i][0] != P:
        P = PY[i][0]
        S = 0
    S += 1
    PY[i].append(("0"*(6-len(str(P)))+str(P)+"0"*(6-len(str(S)))+str(S)))
for i in PY:
    i[0] = i[2]
PY.sort()
for i in PY:
    print(i[3])

Solution (Python):



n,m = map(int, input().split( ))
p = [[] for _ in range(n+1)] 
Ip = [0]*(m+1)
Ix = [0]*(m+1)
for i in range(m):
    pi,yi = map(int, input().split( ))
    p[pi].append((yi,i))

for i in range(n+1):
    p[i].sort()

for pi in range(n+1):
    if p[pi]:
        for k,(yj,j) in enumerate(p[pi]):
            Ip[j] = pi
            Ix[j] = k+1

for i in range(m):
    if Ip[i]:
        print(str(Ip[i]).zfill(6)+str(Ix[i]).zfill(6))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def fillzerostr(n):
    s = str(n)
    while len(s) < 6:
        s = '0' + s
    return s

def main():
    N, M = LI()
    py = []
    py_original = []
    memo = {}
    for _ in range(M):
        P, Y = LI()
        py.append((P, Y))
        py_original.append((P, Y))

    py = sorted(py, key=lambda x: (x[0], x[1]))
    prev_ken = 0
    order = 1
    for i in range(M):
        ken = py[i][0]
        year = py[i][1]
        if prev_ken == ken:
            order += 1
        else:
            order = 1
        memo[py[i]] = fillzerostr(ken) + fillzerostr(order)
        prev_ken = ken

    for i in range(M):
        print(memo[py_original[i]])

main()

Solution (Python):
n, m = map(int, input().split())
c = [list(map(int, input().split())) + [i] for i in range(m)]
d = c[:]
d.sort(key = lambda val: val[1])

k = [0] * 100010
ans = []
for i in d:
    ans.append([i[2], i[0], k[i[0]] + 1])
    k[i[0]] += 1
ans.sort()
for i in ans:
    print(str(i[1]).zfill(6) + str(i[2]).zfill(6))

Solution (Python):
n,m=map(int,input().split())
P=[[] for _ in range(n+1)]
for i in range(m):
    p,y=map(int,input().split())
    P[p].append([y,i+1])
ans=[]
for j in range(n+1):
    if P[j]:
        P[j].sort()
        for i in range(len(P[j])):
            
            ans.append([P[j][i][1],str((j*10**6+i+1)).zfill(12)])
ans.sort()
for i in range(m):
    print(ans[i][1])

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])
L.sort(key=lambda L:(L[0],L[1]))
L[0][1]=1
for i in range(1,m):
    if L[i][0]!=L[i-1][0]:
        L[i][1]=1
    else:
        L[i][1]=L[i-1][1]+1
L.sort(key=lambda L:L[2])
for i in range(m):
    print('{h1:0=6}{h2:0=6}'.format(h1=L[i][0],h2=L[i][1]))

Solution (Python):
import sys 
n, m = map(int, sys.stdin.readline().split())
py = map(int, sys.stdin.read().split())
py = list(zip(py, py))
py = sorted(enumerate(py), key=lambda x: x[1])
dic = {}
ret = {}
for i, j in py:
  tp = j[0]
  if tp in dic:
    dic[tp] += 1
  else:
    dic[tp] = 1
  ps = str(tp)
  ps = '0' * (6 - len(ps)) + ps
  ns = str(dic[tp])
  ns = '0' * (6 - len(ns)) + ns
  ret[i] = ps + ns
for i in ret.values():
  print(i)

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

Solution (Python):
import bisect
from collections import defaultdict
n,m = map(int,input().split())
py = [list(map(int,input().split())) for i in range(m)]
py_sorted = sorted(py)
D = defaultdict(int)
num_arr = []
flag = 0

for a in py_sorted:
  if flag == 0:
    flag = 1
    num_arr.append(a[1])
    a_old = a
    continue
  if a[0] == a_old[0]:
    num_arr.append(a[1])
  else:
    for i,j in enumerate(num_arr):
      D[j] = i+1
    num_arr = []
    num_arr.append(a[1])
  a_old = a

for i,j in enumerate(num_arr):
  D[j] = i+1

for a in py:
  print("%06d%06d"%(a[0],D[a[1]]))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
YPC = []
for c in range(M):
    p, y = MAP()
    p -= 1
    YPC.append((y, p, c))

YPC.sort()
ans = [()] * M
pcnt = [0] * N
for _, p, c in YPC:
    ans[c] = (p + 1, pcnt[p] + 1)
    pcnt[p] += 1

for p, c in ans:
    print(str(p).zfill(6) + str(c).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])
PY.sort()


ans = [0 for i in range(M)]
c = 1
d = 0
for i in range(M):
    
    if c == PY[i][0]:
        d += 1
    else:
        c = PY[i][0]
        d = 1
    ans[PY[i][2]] = '0'*(6-len(str(PY[i][0])))  + str(PY[i][0]) + '0'*(6-len(str(d))) + str(d)
for i in ans:
    print(i)

Solution (Python):
N,M = map(int,input().split())
A = [[] for i in range(N+1)]
B = []
d = {}
for i in range(M):
    p,y = map(int,input().split())
    B.append((p,y))
    A[p].append(y)
for i in range(N+1):
    A[i].sort()
    n = len(A[i])
    for j in range(n):
        d[A[i][j]] = j+1
for i in range(M):
    p,y = B[i]
    q = d[y]
    m = 6 - len(str(p))
    n = 6 - len(str(q))
    ans = "0"*m + str(p) + "0"*n + str(q)
    print(ans)

Solution (Python):
n, m = map(int, input().split())
shi = []
for i in range(m):
  pi, yi = map(int, input().split())
  shi.append([i, pi, yi])
  
shi.sort(key=lambda x:x[1:])

x = 0
for i in range(m):
  x += 1
  shi[i].append("{:06d}{:06d}".format(shi[i][1], x))
  if i != m-1 and shi[i][1] != shi[i + 1][1]:
    x = 0
shi.sort(key=lambda x:x[0])
for i in range(m):
  print(shi[i][3])