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 operator import itemgetter

li = list(map(int, input().split()))
N = li[0]
M=li[1]
L = []
K=[]
for i in range(N):
    L.append([])
    

for i in range(M):
    li = list(map(int, input().split()))
    L[li[0] - 1].append([li[1], i])
    K.append(0)

for i in range(N):
        O = L[i]

        O.sort()
        for j in range(len(O)):
                K[O[j][1]]=str(i+1).zfill(6)+str(j+1).zfill(6)

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

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

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

x.sort()
y = []
prv_p = -1
idx = 1
for xx in x:
    if prv_p != xx[0]:
        prv_p = xx[0]
        idx = 1
    y.append([xx[-1],'{0:06d}{1:06d}'.format(xx[0], idx)])
    idx += 1

y.sort()
for yy in y:
    print(yy[1])

Solution (Python):


n,m = map(int, input().split())
pp =[1]*(n+1)

pl =[1]*(m)
mm={}

for i in range(0,m):
  p,l = map(int, input().split())
  pl[i]=p
  mm[i]=p*100000+l
a=[""]*(m+1)
for k, v in sorted(mm.items(), key=lambda x: x[1]):
  pre=pl[k]
  a[k]="{:06}{:06}".format(pl[k],pp[pre])
  pp[pre]=pp[pre]+1
for i in range(0,m):
  print(a[i])

Solution (Python):
import numpy as np

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

pref_dic = {}
for i in range(N):
    pref_dic[i+1] = []
for e,index in zip(py, range(M)):
    pref = e[0]
    year = e[1]
    
    pref_dic[pref].append((index, year))
        
city_num_dic = {}
for pref in pref_dic.keys():
    pref_string = str(pref)
    if len(pref_string) < 6:
        while len(pref_string) < 6:
            pref_string = "0" + pref_string
    
    in_year_list = np.array(pref_dic[pref])
    if len(in_year_list) == 0:
        continue
    
    year_ =  in_year_list[:, 1]
    city_ = in_year_list[:, 0]
    
    hayaijun_ind = np.argsort(year_)
    for index, i in zip(hayaijun_ind, range(len(hayaijun_ind))):
        city_name = city_[index]
        num = str(i+1)
        if len(num) < 6:
            while len(num) < 6:
                num = "0" + num
        city_num_dic[city_name] = pref_string + num


for city in np.sort(list(city_num_dic.keys())):
    print(city_num_dic[city])

Solution (Python):
n,m = map(int,input().split())
py = list()
for i in range(m):
    l = list(map(int,input().split()))
    l.append(i)
    py.append(l)
py.sort()
ret = list()
c = 1
la = -1
for x in py:
    if la != x[0]:
        c = 1 
    ret.append( (('{0:06d}'.format(x[0])+'{0:06d}'.format(c)),x[2]) )
    c+=1
    la = x[0]
ret.sort(key=lambda x:x[1])
for i in ret:
    print(i[0])

Solution (Python):
from operator import attrgetter


class City:
    def __init__(self, p, y):
        self.p = p
        self.y = y

    def set_num(self, n):
        p = str(self.p)
        _p = list(p)
        l_p = len(_p)
        if l_p < 6:
            num = 6 - l_p
            for i in range(num):
                p = "0" + p

        n = str(n)
        _n = list(n)
        l_n = len(_n)
        if l_n < 6:
            num = 6 - l_n
            for i in range(num):
                n = "0" + n
        self.n = p+n


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

pref_map = {}
for city in cities:
    if city.p in pref_map:
        pref_map[city.p].append(city)
    else:
        pref_map[city.p] = [city]

for v in pref_map.values():
    _cities = sorted(v, key=attrgetter("y"))
    cnt = 1
    for _city in _cities:
        _city.set_num(cnt)
        cnt += 1

for city in cities:
    print(city.n)

Solution (Python):
def output(n, m):
    n = str(n)
    m = str(m)
    return "0"*(6-len(n)) + n + "0"*(6-len(m)) + m

def main():
    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())

    si = [[y, p, i] for i, y, p in zip(range(M), Y, P)]
    si.sort()

    ken = [1] * N
    pp = [0] * M
    for y, p, i in si:
        pp[i] = ken[p-1]
        ken[p-1] += 1

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

main()

Solution (Python):
n,m=[int(x) for x in input().split()]
kens=[[] for x in range(n)]
shis=["" for x in range(m)]
for i in range(m):
    pi,yi=[int(x)-1 for x in input().split()]
    kens[pi].append((i,yi))
    shis[i]=("0"*10+str(pi+1))[-6:]
for ken in kens:
    ken=sorted(ken,key=lambda x :x[1])
    for i in range(len(ken)):
        shis[ken[i][0]]+=("0"*6+str(i+1))[-6:]
for shi in shis:
    print(shi)

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(n):l.append([])
for i in range(m):
    p,y=map(int,input().split())
    l[p-1].append((i,y))
rl=[]
for i in range(n):
    ll=l[i]
    ll.sort(key=lambda x:x[1])
    hd=("000000"+str(i+1))[-6:]
    rr=[(ll[j][0],hd+("000000"+str(j+1))[-6:]) for j in range(len(ll))]
    rl+=rr
rl.sort()
for e in rl:
    print(e[1])

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

hoge = {}

for i in range(m):
    p, y = list(map(int, input().split()))
    if hoge.get(p) == None:
        hoge[p] = [[y, i]]
    else:
        hoge[p].append([y, i])

ID = []

for ken, citylist in hoge.items():
    scitylist = sorted(citylist)
    for j, city in enumerate(scitylist):
       num_padded = '%06d' % (j+1)
       ken_padded = '%06d' % ken
       ID.append([str(ken_padded)+str(num_padded), city[1]])
    
ID_s = sorted(ID, key=lambda x:x[1])

for cityid in ID_s:
    print(cityid[0])

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

PYs = {}

py2nummap = {}
py2 = []
for _ in range(M):
    p, y = list(map(int, input().split()))
    if p not in PYs:
        PYs[p] = []
    PYs[p].append(y)
    py2nummap[(p,y)] = ''
    py2.append((p,y))

for p in sorted(PYs.keys()):
    str_p = '{}'.format(p).zfill(6)
    for idx, c in enumerate(sorted(PYs[p])):
        py2nummap[(p,c)] = (str_p + '{}'.format(idx + 1).zfill(6))


for y in py2:
    
    print(py2nummap[y])

Solution (Python):




def main():
    n, m = list(map(int, input().split()))
    p2y = dict()
    for i in range(m):
        p, y = list(map(int, input().split()))
        p2y.setdefault(p, [])
        p2y[p].append((y, i))
    ids = dict()
    for p in sorted(p2y):
        for i, a in enumerate(sorted(p2y[p])):
            ids[a[1]] = "{:0>6}{:0>6}".format(p, i+1)
    for x in sorted(ids):
        print(ids[x])


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(n):l.append([])
for i in range(m):
    p,y=map(int,input().split())
    l[p-1].append((i,y))
rl=[]
for i in range(n):
    ll=l[i]
    ll.sort(key=lambda x:x[1])
    hd=("000000"+str(i+1))[-6:]
    rr=[(ll[j][0],hd+("000000"+str(j+1))[-6:]) for j in range(len(ll))]
    rl+=rr
rl.sort()
for e in rl:
    print(e[1])

Solution (Python):
n, m =map(int, input().split())
py_array = [[int(x) for x in input().split()]+[y] for x, y in enumerate(range(m), 0)]
py_array = sorted(py_array, key=lambda x:(x[0], x[1]))

base = 1
base2 = 0
res_array = []
for i, j, k in py_array:
    if base == i:
        base2 += 1
    else:
        base = i
        base2 = 1
    res_array.append([str(base).zfill(6), str(base2).zfill(6), k])

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

for i, j, k in res_array:
    print(i+j)

Solution (Python):
from operator import itemgetter

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

city_num = [0 for _ in range(n)]
l = []
for i in range(m):
    p, y = map(int, input().split())
    l.append([i, p, y])

l.sort(key=itemgetter(2))

for i in range(m):
    j, p, y = l[i]
    city_num[p-1] += 1
    idz = str(str(p).zfill(6))
    idk = str(str(city_num[p-1]).zfill(6))
    l[i].append(idz+idk)

l.sort(key=itemgetter(0))
for i in range(m):
    print(l[i][-1])

Solution (Python):
N, M = map(int, input().split())
pref = []
pref_dict = {i+1: [] for i in range(N)}
for _ in range(M):
    P, Y= map(int, input().split())
    pref.append((P, Y))
    pref_dict[P].append(Y)

for p, cities in enumerate(pref_dict.values()):
    pref_dict[p+1] = dict(zip(sorted(cities), range(1, len(cities)+1)))

for i, (p, y) in enumerate(pref):
    print('{0:06d}'.format(pref[i][0]) + '{0:06d}'.format(pref_dict[pref[i][0]][pref[i][1]]))

Solution (Python):
N, M = map(int, input().split())
tupple = []
check_dic = {}
for i in range(M):
    x, y = map(int, input().split())
    li = [i + 1, x, y, 0]
    tupple.append(li)

def int_to_str(num):
    num = str(num)
    text = ""
    for i in range(6 - len(num)):
        text = "0" + text
    return text + num

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

for i in tupple:
    if i[1] not in check_dic:
        check_dic[i[1]] = 1
    else:
        check_dic[i[1]] += 1
    i[3] = int_to_str(i[1]) + int_to_str(check_dic[i[1]])

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

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

Solution (Python):
def get_line():
  return input().split(' ')

class element:
  def __init__(self, P, Y, idx):
    self.P = P
    self.Y = Y
    self.idx = idx
  def __lt__(self, other):
    return self.Y < other.Y

N, M = map(int, get_line())
els = [0] * M
for i in range(M):
  p, y = map(int, get_line())
  els[i] = element(p, y, i)

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

for e in els:
  p_map[e.P - 1].append(e)

ans = [0] * M

for mp in p_map:
  cnt = 1
  for e in sorted(mp):
    ans[e.idx] = "{:06d}{:06d}".format(e.P, cnt)
    cnt = cnt + 1

for e in ans:
  print(e)

Solution (Python):
N, M = map(int, input().split())
tupple = []
check_dic = {}
for i in range(M):
    x, y = map(int, input().split())
    li = [i + 1, x, y, 0]
    tupple.append(li)

def int_to_str(num):
    num = str(num)
    text = ""
    for i in range(6 - len(num)):
        text = "0" + text
    return text + num

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

for i in tupple:
    if i[1] not in check_dic:
        check_dic[i[1]] = 1
    else:
        check_dic[i[1]] += 1
    i[3] = int_to_str(i[1]) + int_to_str(check_dic[i[1]])

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

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

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
L=[]
a=[]
for j in range(m):
  L.append([l[j][0],l[j][1],j])
L.sort()
p=L[0][0]
c=0
for k in range(m):
  if p==L[k][0]:
    a.append([L[k][2],L[k][0],c+1])
    c+=1
  else:
    c=0
    p=L[k][0]
    a.append([L[k][2],L[k][0],c+1])
    c+=1
a.sort()
for x in range(m):
  y=str(a[x][1])
  z=str(a[x][2])
  Y=y.zfill(6)
  Z=z.zfill(6)
  print(Y+Z)

Solution (Python):

n, m = map(int, input().split())
DT = []
RS = []
for i in range(m):
    a, b = map(int, input().split())
    DT.append((a, b, i))
    RS.append('')
DT.sort()
ss = 0
dfz = -1
for I in DT:
    if (I[0] != dfz):
        ss = 0
        dfz = I[0]
    ss += 1
    RS[I[2]] = '%06d%06d' % (I[0], ss)
for I in RS:
    print(I)

Solution (Python):
def myprint(a,b):
    for i in range(1,7):
        if(a//10**i==0):
            keta_a=i
            break
    for i in range(1,7):
        if(b//10**i==0):
            keta_b=i
            break
    
    print("{}{}{}{}".format("0"*(6-keta_a),a,"0"*(6-keta_b),b))


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



for i in range(1,n+1):
    tmp=sorted(data[i].items(),key=lambda x:x[1])
    num=1
    for k in tmp:
        out[k[0]][0]=i
        out[k[0]][1]=num
        num+=1

for o in out:
    myprint(o[0],o[1])

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

city=[]
for i in range(M):
  city.append(list(map(int,input().split())))
  city[i].append(int(i))
city.sort(key=lambda x:x[1])
city.sort(key=lambda x:x[0])

start=city[0][0]
count=0
for i in range(M):
  if city[i][0]!=start:
    start=city[i][0]
    count=1
  else:
    count=count+1
  city[i].append(count)
  
city.sort(key=lambda x:x[2])

for i in range(M):
  print('%06d' % city[i][0],end='')
  print('%06d' % city[i][3])

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

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

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

new_l = []
P = 0
cnt = 1
for num, row in enumerate(l):
    if num != 0:
        if P != row[1]:
            cnt = 1
            
    P = row[1]
    p_name = '{0:06d}'.format(P)
    c_name = '{0:06d}'.format(cnt)
    name = p_name + c_name
    new_l.append([row[0], name])
    cnt += 1

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


for n in new_l:
    print(n[1])

Solution (Python):


import sys
import itertools
import math

N,M=[int(x) for x in input().split()]
C=[[int(x) for x in input().split()] for i in range(M)]

ps=dict()
for c,(p,y) in enumerate(C):
    if not p in ps:
        ps[p]=[]
    ps[p].append((y,c))

qs=[]
for p,cs in ps.items():
    cs.sort()
    qs += [(c,p,i) for i,(y,c) in enumerate(cs)]

qs.sort()

for c,p,i in qs:
    print("{0:0=6}{1:0=6}".format(p,i+1))

Solution (Python):
n, m = list(map(int, input().split()))
pyi = []
for i in range(m):
    tmp = list(map(int, input().split()))
    pyi.append([tmp[0], tmp[1], i])
pyi = sorted(pyi, key = lambda x:x[1])
count_n = [0]*n
for i in range(m):
    count_n[pyi[i][0]-1] += 1
    pyi[i].append(count_n[pyi[i][0]-1])
pyi = sorted(pyi, key = lambda x:x[2])
for i in range(m):
    print(str(pyi[i][0]).rjust(6, "0") + str(pyi[i][-1]).rjust(6, "0"))

Solution (Python):
n, m = list(map(int, input().split()))
pyi = []
for i in range(m):
    tmp = list(map(int, input().split()))
    pyi.append([tmp[0], tmp[1], i])
pyi = sorted(pyi, key = lambda x:x[1])
count_n = [0]*n
for i in range(m):
    count_n[pyi[i][0]-1] += 1
    pyi[i].append(count_n[pyi[i][0]-1])
pyi = sorted(pyi, key = lambda x:x[2])
for i in range(m):
    print(str(pyi[i][0]).rjust(6, "0") + str(pyi[i][-1]).rjust(6, "0"))

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

for i in range(m):
    py[i].append(i)

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

box = []

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

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


for p, c, i in box:
    ans = ""
    if p < 10:
        ans += "00000"
        ans += str(p)
    elif p < 100:
        ans += "0000"
        ans += str(p)
    elif p < 1000:
        ans += "000"
        ans += str(p)
    elif p < 10000:
        ans += "00"
        ans += str(p)
    elif p < 100000:
        ans += "0"
        ans += str(p)
    else:
        ans += str(p)

    if c < 10:
        ans += "00000"
        ans += str(c)
    elif c < 100:
        ans += "0000"
        ans += str(c)
    elif c < 1000:
        ans += "000"
        ans += str(c)
    elif c < 10000:
        ans += "00"
        ans += str(c)
    elif c < 100000:
        ans += "0"
        ans += str(c)
    else:
        ans += str(c)

    print(ans)

Solution (Python):


from collections import Counter

if __name__ == '__main__':
    N, M = map(int, input().split(' '))
    table = [[c + 1] + [int(i) for i in input().split(' ')] for c in range(M)]

    table = sorted(table, key=lambda r: r[2])
    counter = Counter()
    result = []
    for c, p, y in table:
        counter[p] += 1
        result.append((c, '{:06}{:06}'.format(p, counter[p])))

    for c, c_id in sorted(result, key=lambda r: r[0]):
        print(c_id)

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

result = []

for j in range(len(city)):
    city[j].sort()
    for i in range(len(city[j])):
        Y, i1 = city[j][i]
        result.append((i1, j, i + 1))

result.sort()

for ri in result:
    _, a, b = ri
    print("{:06d}{:06d}".format(a, b))

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

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

data = {}

for c in cs:
    if c[0] not in data:
        data[c[0]] = [c]
    else:
        data[c[0]].append(c)

for c_list in data.values():
    c_list.sort(key=lambda c:c[1])

for c_list in data.values():
    for i, c in enumerate(c_list):
        c.append(i)

for c in cs:
    print("{:06}{:06}".format(c[0], c[2]+1))

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

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

dy = {}

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

ans = [" " for _ in range(m)]

for i in range(n):
    if len(py[i]) == 0:
        continue
    temp = sorted(py[i])
    for j in range(len(temp)):
        s = str(i + 1)
        t = 6 - len(s)
        if t > 0:
            s = '0' * t + s
        s2 = str(j + 1)
        t = 6 - len(s2)
        if t > 0:
            s2 = '0' * t + s2
        s = s + s2
        ans[dy[temp[j]]] = s

for x in ans:
    print(x)

Solution (Python):
s=input().split()
n=int(s[0])
m=int(s[1])
l=[[] for i in range(100000)]
d=[{} for i in range(100000)]
inp=[]
for i in range(m):
    s=input().split()
    p=int(s[0])
    y=int(s[1])
    inp.append((p,y))
    l[p-1].append(y)
for i in range(100000):
    l[i].sort()
for i in range(100000):
    cnt=1
    for j in l[i]:
        d[i][j]=cnt
        cnt+=1
for pa in inp:
    L=pa[0]
    R=d[L-1][pa[1]]
    L=str(L)
    R=str(R)
    for i in range(6-len(L)):
        print("0",end="")
    print(L,end="")
    for i in range(6-len(R)):
        print("0",end="")
    print(R)

Solution (Python):
import numpy as np

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

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

Y_argsort = np.argsort(Y)

ans = ["tmp" for x in range(len(Y))]
cnt = [0 for x in range(N)]

for ya in Y_argsort:
    pref_id_padded = '{0:06d}'.format(P[ya])
    city_id = cnt[(P[ya] - 1)] + 1
    cnt[(P[ya] - 1)] += 1
    city_id_padded = '{0:06d}'.format(city_id)
    tmp_id = str(pref_id_padded) + str(city_id_padded)
    ans[ya] = tmp_id

for a in ans:
    print(a)

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

re = {}
city = {}
for i in range(M):
    p, y = list(map(int, input().split()))
    city['{}_{}'.format(p,y)] = i

    if p in re:
        re[p].append(y)
    else:
        re[p] = [y]

ret = [''] * M
for k, v in sorted(re.items()):
    y = sorted(v)
    for i in range(len(y)):
        ret[city['{}_{}'.format(k,y[i])]] = '{:0=6}{:0=6}'.format(k, i+1)

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

Solution (Python):
from itertools import groupby

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

a.sort(key=lambda x: x[1])
r = []
for k, g in groupby(a, key=lambda x: x[1]):
  pre ='{0:06d}'.format(k)
  for j, (i, _, _) in enumerate(sorted(g, key=lambda x: x[2])):
    r.append((i, pre + '{0:06d}'.format(j+1)))
r.sort()
for _, s in r:
  print(s)

Solution (Python):


n,m = map(int, input().split())
d = {}
py = []
for i in range(1,m+1):
    p,y = map(int, input().split())
    py.append((p,y))
    if p not in d:
        d[p] = []
    d[p].append([y,i])

ret = {}
for k in d.keys():
    d[k] = sorted(d[k])
    ret[k] = {}
    for i in range(len(d[k])):
        ret[k][d[k][i][0]] = i+1

for p,y in py:
    print("{:06}{:06}".format(p,ret[p][y]))

Solution (Python):
n, m = map(int, raw_input().split())
array = []
for i in xrange(m):
	p, y = map(int, raw_input().split())
	array.append((y, p, i))

array.sort()
hash_map = dict()
for i in xrange(m):
	y, p, id = array[i]
	if p in hash_map:
		hash_map[p].append((y,id))
	else:
		hash_map[p] = []
		hash_map[p].append((y,id))

res = []
for k, v in hash_map.iteritems():
	key = str(k)
	while len(key) < 6:
		key = '0' + key
	for i in xrange(len(v)):
		year, idx = v[i]
		id = str(i+1)
		while len(id) < 6:
			id = '0' + id
		res.append((idx, key+id))
res.sort()
for i in xrange(len(res)):
	print res[i][1]

Solution (Python):

N, M = map(int, input().split())
PY = [list(map(int, input().split())) + [i, "0" * 12] for i in range(M)] 

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


head = 0
for j, (Pi, Yi, i, dummy) in enumerate(PY):
    if Pi != head:
        tail = 0
        head = Pi
    tail += 1
    
    PY[j][-1] = "{0:06d}{1:06d}".format(head, tail)

PY.sort(key=lambda x: x[2])
for i in range(M): print(PY[i][-1])

Solution (Python):

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



city_dict = {}
ken_city_idx = {}

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

for i,pi,yi in PM:
    
    if pi in ken_city_idx:
        ken_city_idx[pi] += 1
    else:
        ken_city_idx[pi] = 1

    city_dict[i] = "{0:0=6}{1:0=6}".format(pi,ken_city_idx[pi])



for k, v in sorted(city_dict.items(), key=lambda x: x[0]):  
    print(v)

Solution (Python):
import sys
from collections import defaultdict

n, m = map(int, sys.stdin.readline().strip().split(" ", 2))
list_city = defaultdict(list)

for line in sys.stdin:
    p, y = map(int, line.strip().split(" ", 2))
    list_city[p].append(y)

count_city = {}
for p, yl in list_city.iteritems():
    count_city[p] = {y:i+1 for i, y in enumerate(sorted(yl))}

    
sys.stdin.seek(0)
n, m = map(int, sys.stdin.readline().strip().split(" ", 2))

for line in sys.stdin:
    p, y = map(int, line.strip().split(" ", 2))
    print("{:0=6}{:0=6}".format(p, count_city[p][y]))

Solution (Python):
n, m = map(int, input().split())
lst = []
for i in range(m):
    tmplst = list(map(int, input().split()))
    tmplst.append(i)
    lst.append(tmplst)
    
lst.sort()
tmp = 0
for i in range(m):
    if(tmp != lst[i][0]):
        lst[i][1] = 1
        tmp = lst[i][0]
    else:
        lst[i][1] = lst[i-1][1] + 1
        tmp = lst[i][0]
        
lst2 = []
for i in range(m):
    tmplst2 = [str(lst[i][0]).zfill(6)+str(lst[i][1]).zfill(6), lst[i][2]]
    lst2.append(tmplst2)

lst2.sort(key=lambda i: i[1])

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

Solution (Python):
n, m = map(int, input().split())
py = [[0] * 3 for i in range(m)]
for i in range(m):
    py[i][0], py[i][1] = map(int, input().split())
    py[i][2] = i

py.sort()

ans = [""] * m
current = 1
prev = 0
for i in range(m):
    current = py[i][0]
    if current != prev:
        right = 1
        prev = current
    else:
        right += 1

    ans[py[i][2]] = str(current).zfill(6) + str(right).zfill(6)

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

Solution (Python):
n, m = map(int, input().split())
res = [0]*m
p = [[] for _ in range(n)]
for i in range(m):
    pi, yi = map(int, input().split())
    p[pi - 1].append((yi, i))
for pi in range(n):
    p[pi].sort()
    for j in range(len(p[pi])):
        i = p[pi][j][1]
        res[i] = str(pi + 1).zfill(6) + str(j + 1).zfill(6)
print('\n'.join(res))

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

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

ins = []
for p, iys in enumerate(piys):
  if not len(iys):
    continue
  iys.sort(key=lambda iy:iy[1])
  for x in range(1, len(iys) + 1):
    n = "{:06d}{:06d}".format(p, x)
    ins.append((iys[x - 1][0], n))

ins.sort(key=lambda in_:in_[0])
for i, n in ins:
  print(n)

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

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

    ans = [None] * m
    for key in pref:
        pref[key].sort()
        it = pref[key]
        str_k = str(key)
        for j in range(len(it)):
            sj = str(j+1)
            ans[it[j][1]] = "0" * (6-len(str_k)) + str_k + "0" * (6-len(sj)) + sj


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


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split())
from collections import defaultdict
d = defaultdict(lambda:[])
l = []
for i in range(M):
    P,Y = map(int,input().split())
    d[P].append(Y)
    l.append((P,Y))
dd = defaultdict(lambda:{})
for P in d:
    d[P].sort()
    for i in range(len(d[P])):
        dd[P][d[P][i]] = i+1
for i in range(M):
    P,Y = l[i]
    id1 = '0'*(6-len(str(P)))+str(P)
    n = dd[P][Y]
    id2 = '0'*(6-len(str(n)))+str(n)
    print(id1+id2)

Solution (Python):
a = input().split()
a = [int(i) for i in a]
query = []
citydict = dict()
for i in range(a[1]):
	temp = input().split()
	temp = [int(i) for i in temp]
	query.append(temp)
	try:
		citydict[temp[0]].append(temp[1])
	except:
		citydict[temp[0]] = [temp[1]]
		
indexdict = dict()
for i in citydict:
	citydict[i] = sorted(citydict[i])
	indexdict[i] = dict()
	for j in range(len(citydict[i])):
		indexdict[i][citydict[i][j]] = j
		
for i in query:
	print ("%06d%06d" % (i[0],indexdict[i[0]][i[1]] + 1))

Solution (Python):
n, m = map(int, raw_input().split())
array = []
for i in xrange(m):
	p, y = map(int, raw_input().split())
	array.append((y, p, i))

array.sort()
hash_map = dict()
for i in xrange(m):
	y, p, id = array[i]
	if p in hash_map:
		hash_map[p].append((y,id))
	else:
		hash_map[p] = []
		hash_map[p].append((y,id))

res = []
for k, v in hash_map.iteritems():
	key = str(k)
	while len(key) < 6:
		key = '0' + key
	for i in xrange(len(v)):
		year, idx = v[i]
		id = str(i+1)
		while len(id) < 6:
			id = '0' + id
		res.append((idx, key+id))
res.sort()
for i in xrange(len(res)):
	print res[i][1]

Solution (Python):
n, m = map(int, input().split())
x = [list(map(int, input().split())) + [i] for i in range(m)]
x.sort()
tmp = 0
k = 0
z = [None for _ in range(m)]
for i in range(m):
    if tmp == x[i][0]:
        k += 1
    else:
        k = 1
        tmp = x[i][0]
    z[x[i][2]] = '{0:06d}{1:06d}'.format(x[i][0], k)
for i in range(m):
    print(z[i])

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

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

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

for i in range(m):
    ok,ng = 0,len(city[p[i]])
    while ng-ok > 1:
        mid = (ok+ng)//2
        if city[p[i]][mid] <= y[i]:
            ok = mid
        else:
            ng = mid

    print('{:06d}{:06d}'.format(p[i], ok+1))

Solution (Python):
import heapq

N, M = map(int, input().split())
S = ["" for m in range(M)]

D = {}
for m in range(M):
    P, Y = map(int, input().split())
    listP = D.setdefault(P, [])
    heapq.heappush(listP, (Y, m))

for p, l in D.items():
    for i in range(len(l)):
        y, m = heapq.heappop(l)
        S[m] = format(p, "06") + format(i + 1, "06")

for s in S:
    print(s)

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

for k in range(M):
    L[k].append(k)
L = sorted(L)

A = [[L[0][0],1,L[0][2]]]
t = 1

for k in range(1,M):
    if L[k-1][0] != L[k][0]:
        t = 1
    else:
        t += 1
    A.append([L[k][0],t,L[k][2]])

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

for a in A:
    print(str(a[0]).zfill(6) + str(a[1]).zfill(6))

Solution (Python):
from operator import itemgetter

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


for i in range(m):
    py[i].append(i)

py.sort(key = itemgetter(1))
py.sort(key = itemgetter(0))

py[0].append(str(py[0][0]).zfill(6)+str(1).zfill(6))

if m == 0:
    print(py[0][3])
    exit()

for i in range(1,m):
    if py[i][0]!=py[i-1][0]:
        py[i].append(str(py[i][0]).zfill(6)+str(1).zfill(6))
    else:
        py[i].append(str(int(py[i-1][3])+1).zfill(12))

py.sort(key = itemgetter(2))

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

Solution (Python):

from collections import defaultdict
def solve():
    N, M = map(int, input().split())
    PY = sorted([tuple(map(int, input().split()))+(i,) for i in range(1,M+1)])
    x = defaultdict(int)
    ID = sorted([(i, '{0:0>6d}{1:0>6d}'.format(p,x[p])) for p,y,i in PY if x.update({p:x[p]+1}) is None])
    res = '\n'.join([id_[1] for id_ in ID])
    return res
    
if __name__ == '__main__':
    print(solve())

Solution (Python):
def getN():
    return int(input())


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


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

n,m = getNM()

pres = [[] for i in range(n)]
cities = []
for i in range(m):
    n,m = getNM()
    cities.append([i, n,m]) 

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

for i, c in enumerate(cities):
    pres[c[1]-1].append([c[0]])

buf = []
for i, p in enumerate(pres):
    for j, c in enumerate(p):
        buf.append([c[0], "{0:06d}".format(i+1) + "{0:06d}".format(j+1)])


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

Solution (Python):
def getN():
    return int(input())


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


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

n,m = getNM()

pres = [[] for i in range(n)]
cities = []
for i in range(m):
    n,m = getNM()
    cities.append([i, n,m]) 

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

for i, c in enumerate(cities):
    pres[c[1]-1].append([c[0]])

buf = []
for i, p in enumerate(pres):
    for j, c in enumerate(p):
        buf.append([c[0], "{0:06d}".format(i+1) + "{0:06d}".format(j+1)])


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

Solution (Python):
N, M = map(int, input().split())
d = {}
for i in range(M):
  P, Y = map(int, input().split())
  if P in d:
    d[P].append((Y, i))
  else:
    d[P] = [(Y, i)]
for i in d:
  d[i].sort()
ans = {}
for i in d:
  for j in range(len(d[i])):
    ans[d[i][j][1]] = 1000000000000 + 1000000 * i + j + 1
for i in range(M):
  print(str(ans[i])[1:])

Solution (Python):
N, M = map(int, input().split())
X = [[] for _ in range(N)]
ans_list = ["a" for i in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    X[p - 1].append((i, y))
for i in range(N):
    if len(X[i]) != 0:
        X[i].sort(key=lambda x: x[1])
        for j in range(len(X[i])):
            ans_list[X[i][j][0]] = "{:06}".format(
                i + 1) + "{:06}".format(j + 1)

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