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):
P,C = map(int,input().split())
pref = [[] for _ in range(P)]
city = []
for ci in range(C):
  p,y = map(int,input().split())
  city.append([p-1])
  pref[p-1].append([y,ci])
cinp = []
for pi in range(P):
  pref[pi].sort()
  for j in range(len(pref[pi])):
    citycode = pref[pi][j][1]
    city[citycode].append(j)
for ci in range(C):
  pnow = city[ci][0]
  inow = city[ci][1]
  try:
    ans = (pnow+1) * 10 ** 6 + (inow+1)
  except:
    print(pnow,inow,p,cinp)
  ANS = str(ans)
  print( '0' * (12 - len(ANS)) + ANS)

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

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

ans = [None]*M

for i, d in enumerate(D): 
  d.sort()
  for k, (y, j) in enumerate(d): 
    ans[j] = str(i+1).zfill(6) + str(k+1).zfill(6) 

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

Solution (Python):
from collections import defaultdict
 
n, m = [int(x) for x in input().split(' ')]
py = [tuple(input().split(' ')) for _ in range(m)]
 
d = defaultdict(list)
 
for x, y in py:
    d[x].append(int(y))
 
ans = {}
 
for k, v in d.items():
    for i, x in enumerate(sorted(v), start=1):
        ans[(k, str(x))] = k.zfill(6) + str(i).zfill(6)
 
for x in py:
    print(ans[x])

Solution (Python):
from collections import defaultdict

n, m = [int(x) for x in input().split(' ')]
py = [tuple(input().split(' ')) for _ in range(m)]

d = defaultdict(list)

for x, y in py:
    d[x].append(int(y))

ans = {}

for k, v in d.items():
    for i, x in enumerate(sorted(v), start=1):
        ans[(k, str(x))] = k.zfill(6) + str(i).zfill(6)

for x in py:
    print(ans[x])

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

towns = [list(map(int, input().split())) + [i] for i in range(m)]
sort_towns = sorted(towns, key = lambda x : (x[0], x[1]))

prev_pref = 1
town_no = 1
for i in range(len(sort_towns)):
    pref = sort_towns[i][0]
    town = sort_towns[i][1]
    if not prev_pref == pref:
        town_no = 1
        prev_pref = pref
        sort_towns[i].append(town_no)
    sort_towns[i].append(town_no)
    town_no += 1
sort_towns = sorted(sort_towns, key=lambda x : x[2])
for i in range(len(sort_towns)):
    print(str(sort_towns[i][0]).zfill(6) + str(sort_towns[i][3]).zfill(6))

Solution (Python):
import bisect
n,m=map(int, input().split())
pl=[0]*100000
yl=[0]*100000
ol=[[] for i in range(100001)]
for i in range(m):
    pl[i],yl[i] = map(int, input().split())
    ol[pl[i]].append(yl[i])
for i in range(1,n+1):
    ol[i].sort()
for i in range(m):
    print("%06d%06d" % (pl[i], bisect.bisect_right(ol[pl[i]], yl[i])))

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

l.sort()

memo = []
mae = 0
cnt = 0
for i in range(m):
    if i == 0:
        mae = l[0][0]
        cnt = 1
    else:
        if mae == l[i][0]:
            cnt += 1
        else:
            mae = l[i][0]
            cnt = 1
    memo.append([l[i][2], str(l[i][0]).zfill(6) + str(cnt).zfill(6)])

memo.sort()

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

Solution (Python):
N,M = map(int,input().split())
city_d = {}
ans_l = ["" for _ in range(M)]
for i in range(M):
    P,Y = map(int,input().split())
    city_d.setdefault(P,[])
    city_d[P].append([Y,i])

for p,y_orgnum in city_d.items():
    for j,sorted_y_orgnum in enumerate(sorted(y_orgnum,key=lambda x:x[0])):
        ans_l[sorted_y_orgnum[1]] = str(p).zfill(6) + str(j+1).zfill(6)

for ans in ans_l:
    print(ans)

Solution (Python):
n, m = map(int, input().split())
py = {}
for i in range(m):
    p, y = map(int, input().split())
    py.setdefault(p, [])
    py[p].append([i + 1, y])
for i in py:
    py[i].sort(key = lambda x: x[1])
    for j in range(len(py[i])):
        py[i][j][1] = j + 1
city = []
for i in py:
    for j in py[i]:
        city.append([j[0], i, j[1]])
city.sort()
for i in city:
    print(str(i[1]).rjust(6, "0") + str(i[2]).rjust(6, "0"))

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

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

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

id = [0] * M

for p, city in enumerate(cities) :
    city.sort(key = lambda A : A[1])
    for index, (i, year) in enumerate(city) :
        id[i] = '{pre:06}{i:06}'.format(pre = p + 1, i = index + 1)

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

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


def sread():
    return input()


def aread_int():
    tmp = input().split()
    ret = [int(i) for i in tmp]
    return ret


def aread_str():
    return input().split()


def fst(t):
    return t[0]


def snd(t):
    return t[1]


def thd(t):
    return t[2]


if __name__ == '__main__':
    n, m = map(int, input().split())
    l = []
    ans = []
    for i in range(m):
        p, y = map(int, input().split())
        l.append((p, y, i))

    l = sorted(l)
    end = 0
    for i in range(n):
        begin = end
        while end < len(l) and fst(l[end]) == i + 1:
            end += 1
        town = l[begin:end]
        sorted(town, key=lambda x: snd(x))
        tmp = 1
        for e in town:
            ans.append((fst(e), tmp, thd(e)))
            tmp += 1

    ans = sorted(ans, key=lambda x : thd(x))
    for e in ans :
        birth = str(fst(e))
        rate = str(snd(e))
        print(birth.zfill(6) + rate.zfill(6))

Solution (Python):
N, M = map(int, input().split())
data = []
for i in range(M):
    P, Y = list(map(int, input().split()))
    data.append((i, P, Y))
data = sorted(data, key = lambda x:(x[1],x[2]))

city_id = []
cnt = 0
pref = 1
for ci in data:
  if ci[1] != pref:
    pref = ci[1]
    cnt = 0
  cnt += 1
  id = '{0:0>6}{1:0>6}'.format(pref, cnt)
  city_id.append([ci[0], id])
city_id.sort(key=lambda x: x[0])
for ci in city_id:
  print(ci[1])

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

year_of_p_dict = {}
for py in pys:
    p,y = py
    if not p in year_of_p_dict:
        year_of_p_dict[p] = []
    year_of_p_dict[p].append(y)

for p,ys in year_of_p_dict.items():
    ys.sort()
    ys_idx_dict = {}
    for i,y in enumerate(ys):
        ys_idx_dict[y] = i+1
    year_of_p_dict[p] = ys_idx_dict

for py in pys:
    p,y = py
    ans = str(p).zfill(6) + str(year_of_p_dict[p][y]).zfill(6)
    print(ans)

Solution (Python):
n,m = map(int, input().split())
INF = 100010
array = [[] for _ in range(n)]
ans = [0 for _ in range(m)]

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

for i, elem in enumerate(array):
    elem = sorted(elem)
    for index, e in enumerate(elem):
        str = "{0:06d}{1:06d}".format(i+1, index+1)
        ans[e[1]] = str
print("\n".join(ans))

Solution (Python):
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	n,m = map(int,input().split())
	py = defaultdict(list)
	si_ban = []
	for _ in range(m):
		x,y = map(int,input().split())
		si_ban.append(y)
		py[x].append(y)
	ans = {}
	for k,v in py.items():
		v.sort()
		for i in range(1,len(v)+1):
			ans[v[i-1]] = str(k).zfill(6) + str(i).zfill(6)
	for i in si_ban:
		print(ans[i])

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Solution (Python):


class CityClass:
    def __init__(self, pref, year):
        self.pref = pref
        self.year = year
        self.num = 0

    def __lt__(self, other):
         return self.year < other.year


city_order_list = []

n, m = map(int, input().split())
pref_list = []

for i in range(n):
    pref_list.append([])

for i in range(m):
    pref, year = map(int, input().split())
    new_city = CityClass(pref, year)
    pref_list[pref-1].append(new_city)
    
    
    city_order_list.append(new_city)

for city_list in pref_list:
    city_list.sort()

    num = 1
    for city in city_list:
        city.num = num
        num += 1 

for city in city_order_list:
    pref_num_str = str(city.pref).zfill(6)
    city_num_str = str(city.num).zfill(6)
    print('{}{}'.format(pref_num_str,city_num_str))

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

city_inf.sort(key=lambda x:x[2])
order_counter = {}

for list in city_inf:
    if list[1] in order_counter.keys():
        order_counter[list[1]] += 1
        list.append(order_counter[list[1]])
    else:
        order_counter[list[1]] = 1
        list.append(1)

city_inf.sort(key=lambda x:x[0])
zero_p = ''
zero_y = ''
for list in city_inf:
    zero_p = '0'*(6-len(str(list[1])))
    zero_y = '0'*(6-len(str(list[3])))
    list.append(zero_p + str(list[1]) + zero_y + str(list[3]))
    print(list[4])

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

def main():
	n, m = map(int, input().strip().split())
	city = [[] for _ in range(m)]
	for i in range(m):
		p, y = map(int, input().strip().split())
		city[i] = [i, p, y]
	city.sort(key=itemgetter(2))
	city.sort(key=itemgetter(1))
	id = 0
	for i in range(m):
		if i != 0 and city[i][1] != city[i-1][1]:
			id = 1
		else:
			id += 1
		city[i].append(id)
	city.sort(key=itemgetter(0))
	for i in range(m):
		print("{:06}{:06}".format(city[i][1], city[i][3]))
if __name__ == '__main__':
	main()

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

city_inf=[]

for i in range(m):
	array=[i]
	array.extend(list(map(int,input().split())))
	city_inf.append(array)


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


order_counter={}


for list in city_inf:
	if list[1] in order_counter.keys():
		order_counter[list[1]]+=1
		list.append(order_counter[list[1]])
	else:
		order_counter[list[1]]=1
		list.append(1)


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


zero_p=""
zero_y=""

for list in city_inf:
	zero_p="0"*(6-len(str(list[1])))
	zero_y="0"*(6-len(str(list[3])))
	list.append(zero_p+str(list[1])+zero_y+str(list[3]))
	print(list[4])

Solution (Python):
n,m=map(int,input().split());li=[]
for i in range(m):
  li.append(list(map(int,input().split()))+[i])
li.sort()
cac=li[0][0];o=2
li[0][1]=1
for g in li[1:]:
  if g[0]!=cac:
    cac=g[0]
    o=1
  g[1]=o
  o+=1
li.sort(key=lambda x:x[-1])
for g in li:
  print("%06d"%g[0]+"%06d"%g[1])

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

py = [[] for _ in range(m)]
"""
for i in range(m):
    py.append(input().split())
"""    
for i in range(m):
    a, b = map(lambda x: int(x), input().split())
    py[i].append([a,b,i])






py.sort()



ken = 1
city = 1

for i in range(m):
    if py[i][0][0] == ken:
        py[i][0][1] = city
        city += 1
    else:
        ken = py[i][0][0]
        city = 1
        py[i][0][1] = city
        city += 1
        


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



for i in range(m):
    print('{:0=6}{:0=6}'.format(py[i][0][0],py[i][0][1]))

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()
city=py[0][0]
cnt=0
for i in range(m):
  if py[i][0] == city:
    cnt+=1
    py[i].append(cnt)
  else:
    city=py[i][0]
    cnt=1
    py[i].append(cnt)
for i in range(m):
  num=str(py[i][0]).zfill(6)+str(py[i][3]).zfill(6)
  py[i].append(num)
py.sort(key=lambda x:x[2])
for i in range(m):
  print(py[i][4])

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

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

city_id = []
cnt = 0
pref = 0
for ci in city:
  if ci[1] != pref:
    pref = ci[1]
    cnt = 0
  cnt += 1
  id = '{0:0>6}{1:0>6}'.format(pref, cnt)
  city_id.append([ci[0], id])
city_id.sort(key=lambda x: x[0])
for ci in city_id:
  print(ci[1])

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    cities = list(map(string_to_int, inputs))
    prefecutures = {}
    for i, c in enumerate(cities):
        p = c[0]
        y = c[1]
        if p not in prefecutures:
            prefecutures[p] = []
        prefecutures[p].append((i, p, y))

    ids = {}
    for p in prefecutures.keys():
        prefecutures[p].sort(key=lambda x: x[2])
        for order, c in enumerate(prefecutures[p]):
            [ic, pc, yc] = c
            ids[ic] = "{:06d}{:06d}".format(p, order+1)

    ret = ""
    for i in range(0, M):
        ret += ids[i] + "\n"

    return ret.strip()


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

Solution (Python):
dct = []
N, M = map(int, input().split())
data = {k+1: [] for k in range(N)}

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

for v in data.values():
  v.sort(key=lambda x:x[1])

ans = {}
for k, v in data.items():
  for i, j in enumerate(v):
    ans[j[0]] = "{0:06d}".format(k) + "{0:06d}".format(i+1)

for i in ans.values():
  print(i)

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

C = []
for i in range(M):
    P, Y = list(map(int, input().split()))
    C.append((i, P, Y))
C = sorted(C, key=lambda x:x[1])

K, L = [], []
p = C[0][1]
for c in C:
    if c[1]!=p:
        p = c[1]
        L += [ (k[0], k[1], i+1) for i, k in enumerate(sorted(K, key=lambda x:x[2]))]
        K = []

    K.append(c)

L += [ (k[0], k[1], i+1) for i, k in enumerate(sorted(K, key=lambda x:x[2]))]

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

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

n = 1
now = PY[0][0]
for py in PY:
    if now != py[0]:
        now = py[0]
        n = 1
    py[1] = n
    n += 1

PY.sort(key=lambda val: val[2])

for py in PY:
    print('{:0>6}'.format(py[0]) + '{:0>6}'.format(py[1]))

Solution (Python):
n,m  = list(map(int,input().split(" ")))
data = []
for i in range(m):
  p,y  = list(map(int,input().split(" ")))
  data.append((i,p,y))
data = sorted(data, key = lambda x:(x[1],x[2]))
ans = []
now_i = 0
now_p = 0
for d in data:
  i,p,y = d
  if(now_p != p):
    now_p = p
    now_i = 1
  else:
    now_i += 1
  ans.append((i,str(p).zfill(6)+str(now_i).zfill(6)))
ans = sorted(ans,key = lambda x:x[0])
for (i,t) in ans:
  print(t)

Solution (Python):
import copy

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

py_sorted = copy.deepcopy(py)
py_sorted = sorted(py_sorted,key=lambda x :(x[0],x[1]))

id_y = {}
pref_id= py_sorted[0][0]
city_id=1

for e in py_sorted:
  if pref_id != e[0]:
    pref_id = e[0]
    city_id =1
  id_y['{}_{}'.format(e[0],e[1])] = '{:06d}{:06d}'.format(e[0],city_id)
  city_id += 1
  
for pyi in py:
  print(id_y['{}_{}'.format(pyi[0],pyi[1])])

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

List.sort(key=lambda x:x[1])
dic = {}

for k in range(M):
    dic[List[k][0]] = 0

ans = []

for l in range(M):
    dic[List[l][0]] += 1
    ans.append([List[l][0]*10**6+dic[List[l][0]],List[l][2]])

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

for m in range(M):
    num = str(ans[m][0])
    print(num.zfill(12))

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

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

for i in range(M):
  X[i].append(i)

X.sort(key=lambda X:(X[0],X[1]))
X[0].append(1)
for i in range(M-1):
	if X[i+1][0] == X[i][0]:
		X[i+1].append(X[i][3]+1)
	else:
		X[i+1].append(1)

X.sort(key=lambda X:X[2])
for i in range(M):
  a = str(X[i][0])
  b = str(X[i][3])
  print("0"*(6-len(a))+a+"0"*(6-len(b))+b)

Solution (Python):
import sys

n, m = (int(x) for x in sys.stdin.readline().split())
city_list = [[int(x) for x in sys.stdin.readline().split()] for y in range(m)]
print_list = [0] * m
count = 0
pref_dic = {}
for i in range(len(city_list)):
    city_list[i].append(i)
city_list.sort(key=lambda x: (x[0], x[1]))
for i in city_list:
    pref = i[0]
    pref_id = "0" * (6 - len(str(pref))) + str(pref)
    city_id = ""
    if pref in pref_dic:
        pref_dic[pref] += 1
        city = pref_dic[pref]
        city_id = "0" * (6 - len(str(city))) + str(city)
    else:
        pref_dic[pref] = 1
        city_id = "0" * (6 - len(str(1))) + str(1)
    print_list[i[2]] = pref_id + city_id

for i in print_list:
    print(i)

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

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


PY.sort(key = lambda x:x[1])
for p,_,i in PY:
    count[p-1] += 1
    ans[i] = str(p).zfill(6) + str(count[p-1]).zfill(6)

for a in ans:
    print(a)

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

p_count = [1] * (N + 1)
for r in sorted(pairs, key=lambda x: x[1]):
    r.append("{:06}{:06}".format(r[0], p_count[r[0]]))
    p_count[r[0]] += 1

print("\n".join((r[2] for r in pairs)))

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

p_y_li = [list(map(int, (input() + " {}".format(i)).split())) for i in range(m)]

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

li = [0 for _ in range(n)]
for i in range(m):
    ans = ""
    p = p_y_li[i][0]
    li[p-1] += 1
    x = li[p-1]
    ans = str(p).zfill(6) + str(x).zfill(6)
    p_y_li[i].append(ans)

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

Solution (Python):


input=open(0).readline

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

py.sort()

ans=[]

pre_cty=0
cnt=1
for i in range(m):
    p,y,idx=py[i]
    cty=p
    if pre_cty==cty:
        cnt+=1   

    else:
        pre_cty=p
        cnt=1
    
    p=str(p).zfill(6)
    x=str(cnt).zfill(6)
    ans.append((idx,p+x))

ans.sort()

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

Solution (Python):
n,m=map(int,input().split())
info=[]
for i in range(m):
    info.append(list(map(int,input().split())))
    info[i].append(i)
info2=sorted(info,key=lambda x:x[1])
info3=sorted(info2)


num=info3[0][0] 
city=0 

for i in range(m):
    number=""
    if info3[i][0]==num:
        city+=1
        l1=6-len(str(num)) 
        l2=6-len(str(city)) 
        number+=str(0)*l1+str(num)+str(0)*l2+str(city)
        info3[i].append(number)
    else: 
        num=info3[i][0]
        city=1
        l1=6-len(str(num)) 
        l2=6-len(str(city)) 
        number+=str(0)*l1+str(num)+str(0)*l2+str(city)
        info3[i].append(number)

info4=sorted(info3,key=lambda x:x[2])
for i in range(m):
    print(info4[i][3])

Solution (Python):
a, b = map(int, input().split())
c = []
f = [0] * a
for i in range(b):
    d, e = map(int, input().split())
    c.append([d, e, i, ""])
c = sorted(c, key=lambda x: (x[0], x[1]))
for i in range(b):
    f[c[i][0]-1] += 1
    c[i][3] = ("000000" + str(c[i][0]))[-6:] + ("000000" + str(f[c[i][0]-1]))[-6:]
c = sorted(c, key=lambda x: x[2])
for i in range(len(c)):
    print(c[i][3])

Solution (Python):
import bisect
N, M = map(int,input().split())
P = []
Y = []
B = [[] for _ in range(N)]
for _ in range(M):
    p, y = map(int,input().split())
    P.append(p)
    Y.append(y)
    B[p-1].append(y)

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

for p, y in zip(P, Y):
    print("{:06}{:06}".format(p, bisect.bisect_left(B[p-1], y) + 1))

Solution (Python):
import numpy as np

pn,cn=list(map(int,input().split()))
x=list(list(map(int,input().split())) for _ in range(cn))
y=list([range(cn)])
z=np.hstack([np.array(x),np.array(y).T])
al=sorted(z,key=lambda a:(a[0],a[1]))

res=['']*cn
cnt=1

for i in range(cn):
	if i>0:
		if al[i-1][0]==al[i][0]:
			cnt+=1
		else:
			cnt=1
	res[al[i][2]]=str(1000000+al[i][0])[1:7]+str(1000000+cnt)[1:7]

for i in range(cn):
	print(res[i])

Solution (Python):
def main():
    _, m = map(int, input().split())
    cities = [[i] + list(map(int, input().split())) for i in range(m)]
    cities = sorted(cities, key=lambda x: x[2])
    orders = {}
    ids = ['' for _ in range(m)]
    for c in cities:
        p = c[1]
        if p in orders:
            orders[p] += 1
        else:
            orders[p] = 1
        ids[c[0]] = '{0:06d}{1:06d}'.format(p, orders[p])
    [print(i) for i in ids]


main()

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

def f(pi,num):
    s = str(pi).zfill(6)+str(num+1).zfill(6)
    return s

shi = []
for i in range(0,m):
    shi.append([i]+list(map(int,input().split())))
shi.sort(key=lambda x:x[1])
p = shi[0][1]
pm = []
ans = []
for i in range(0,m):
    if shi[i][1] == p:
        pm.append([shi[i][0],shi[i][2]])
    else:
        pm.sort(key=lambda x:x[1])
        for j in range(0,len(pm)):
            ans.append([pm[j][0],f(shi[i-1][1],j)])
        pm = []
        pm.append([shi[i][0],shi[i][2]])
        p = shi[i][1]
pm.sort(key=lambda x:x[1])
for j in range(0,len(pm)):
    ans.append([pm[j][0],f(shi[m-1][1],j)])

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

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

ln = [''] * M
for k in adict.keys():
    for j,d in enumerate(sorted(adict[k],key=lambda x: x[1])):
        num = d[0]
        ln[num] = str(k).zfill(6) + str(j+1).zfill(6)

for z in ln:print(z)

Solution (Python):
n,m=map(int,input().split())
s=[list(map(int, input().split())) for i in range(m)] 
for i in range(m):
    s[i].append(i+1)
a=0
s.sort()
for i in range(m):
    if i>=1:
        if s[i][0]!=s[i-1][0]:
            a=0
        
    s[i].append(str(0)*(6-len(str(s[i][0])))+str(s[i][0]))
    s[i].append(str(0)*(6-len(str(a+1)))+str(a+1))
    a+=1
s.sort(key=lambda x:x[2])
for i in range(m):
    print(s[i][3]+s[i][4])

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

sorted_indices = sorted(range(len(pref_and_year)),
                        key=lambda k: pref_and_year[k][1])
sorted_perf_and_year = sorted(pref_and_year, key=lambda x: x[1])
count = [0] * N
res = []
for i, x in zip(sorted_indices, sorted_perf_and_year):
    count[x[0]-1] += 1
    auth_number = str(x[0]).zfill(6) + str(count[x[0]-1]).zfill(6)
    res.append((i, auth_number))
res = sorted(res, key=lambda x: x[0])
for x in res:
    print(x[1])

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

sorted_indices = sorted(range(len(pref_and_year)),
                        key=lambda k: pref_and_year[k][1])
sorted_perf_and_year = sorted(pref_and_year, key=lambda x: x[1])
count = [0 for _ in range(N)]
res = []
for i, x in zip(sorted_indices, sorted_perf_and_year):
    count[x[0]-1] += 1
    auth_number = str(x[0]).zfill(6) + str(count[x[0]-1]).zfill(6)
    res.append((i, auth_number))
res = sorted(res, key=lambda x: x[0])
for x in res:
    print(x[1])

Solution (Python):
N, M = map(int, input().split())
lst = list()
for i in range(M):
    P, Y = map(int, input().split())
    lst.append((Y, i, P))
lst.sort()

cnt = [1] * (N + 1)
ans = list()
for Y, i, P in lst:
    id = str(P).zfill(6) + str(cnt[P]).zfill(6)
    cnt[P] += 1
    ans.append((i, id))
ans.sort()
for i, id in ans:
    print(id)

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))
ans = ['']*(M)
L.sort(key=lambda x:(x[0], x[1]))
before = L[0][0]
num = 0
for i in range(M):
  if L[i][0] == before:
    num += 1
    id = '{:06d}'.format(L[i][0]) + '{:06d}'.format(num)
    ans[L[i][2]] = id
  else:
    num = 1
    id = '{:06d}'.format(L[i][0]) + '{:06d}'.format(num)
    ans[L[i][2]] = id
    before = L[i][0]
for city in ans:
  print(city)

Solution (Python):
N, M = map(int, input().split())
cities = []
for i in range(0, M):
	P, Y = map(int, input().split())
	cities.append([i, P, Y])
cities.sort(key = lambda v: v[2])
cities.sort(key = lambda v: v[1])
idkeylist = [[cities[0][0], cities[0][1], 1]]
cnt = 2
for i in range(1, M):
	if cities[i][1] != idkeylist[-1][1]:
		idkeylist.append([cities[i][0], cities[i][1], 1])
		cnt = 2
	else:
		idkeylist.append([cities[i][0], cities[i][1], cnt])
		cnt += 1
idkeylist.sort(key = lambda v: v[0])
for i in range(0, M):
	ansP = str(idkeylist[i][1])
	while len(ansP) < 6:
		ansP = '0' + ansP
	ansT = str(idkeylist[i][2])
	while len(ansT) < 6:
		ansT = '0' + ansT
	print(ansP+ansT)

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

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


ans = []
cnt = 1
for i in range(m):
    number = '{:0=6}'.format(l[i][0])
    if i == 0:
        cnt = 1
    else:
        if l[i-1][0]==l[i][0]:
            cnt += 1
        else:
            cnt = 1
    number += '{:0=6}'.format(cnt)
    ans.append([number,l[i][2]])
    
ans.sort(key=lambda x:x[1])


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

Solution (Python):
import numpy as np

n,m = map(int,input().split())
d = {}
ans = ["" for i in range(m)]

for i in range(m):
    p,y = map(int,input().split())
    if p not in d:
        d[p] = [[y,i]]
    else:
        d[p].append([y,i])
for key in d.keys():
    temp = d[key]
    temp.sort(key=lambda x:x[0])
    city = key
    if len(list(str(city))) < 7:
        city = "0" * (6 - len(list(str(city)))) + str(city)
    for i in range(len(temp)):
        if len(list(str(i+1))) < 7:
            y = "0"*(6-len(list(str(i+1))))+str(i+1)
            
        ans[temp[i][1]] = city+y

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

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

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

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

city = [1] * (n + 1)
for i in range(m):
    (i, c, y) = dat[i]
    r = city[c]
    city[c] += 1
    res[i] = "%06d%06d" % (c, r)

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

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

n, m = map(int, input().split())
l = []
num = [0] * n
ans = [""] * m

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

l.sort()


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

for a in ans:
    print(a)

Solution (Python):
import sys
n,m=map(int,input().split())
if m==1:
  a,b=map(int,input().split())
  print(str(a).zfill(6)+str(m).zfill(6));sys.exit()
cities=[None]*m
for i in range(m):
  p,y=map(int,input().split())
  cities[i]=[p,y,i]
cities.sort(key=lambda x:x[1]);cities.sort(key=lambda x:x[0])
i=0
c=1
while True:
  cities[i].append(c)
  c+=1
  if i!=m-1 and cities[i][0]!=cities[i+1][0]:c=1
  elif i==m-1:break
  i+=1
cities.sort(key=lambda x:x[2])
for i in cities:
  print(str(i[0]).zfill(6)+str(i[3]).zfill(6))

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

yp_dic={}
yplist=[]
for i in range(M):
  p,y=map(int,input().split())
  if p not in yp_dic:
    yp_dic[p]=[]
  yp_dic[p].append(y)
  yplist.append((y,p))

all_dic={}
for key in yp_dic:
  yp_dic[key].sort()
  for i,y in enumerate(yp_dic[key]):
    all_dic[y]=i+1


for y,p in yplist:
  id="{:0>6}{:0>6}".format(p,all_dic[y])
  print(id)

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

p_count = [1] * (N + 1)
for r in sorted(pairs, key=lambda x: x[1]):
    r.append("{:06d}{:06d}".format(r[0], p_count[r[0]]))
    p_count[r[0]] += 1

print("\n".join((r[2] for r in pairs)))

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

p_count = [1] * (N + 1)
for r in sorted(pairs, key=lambda x: x[1]):
    r.append("{:06d}{:06d}".format(r[0], p_count[r[0]]))
    p_count[r[0]] += 1

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

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

yp_dic={}
yplist=[]
for i in range(M):
  p,y=map(int,input().split())
  if p not in yp_dic:
    yp_dic[p]=[]
  yp_dic[p].append(y)
  yplist.append((y,p))

for key in yp_dic:
  yp_dic[key].sort()


all_dic={}
for pref,ylist in yp_dic.items():
  pref_dic={}
  for i,y in enumerate(ylist):
    pref_dic[y]=i+1
  all_dic[pref]=pref_dic


for y,p in yplist:
  id="{:0>6}{:0>6}".format(p,all_dic[p][y])
  print(id)