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

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    P = tuple(map(int, input().split()) for _ in range(M))
    A = sorted((p, y, i) for i, (p, y) in enumerate(P))
    ans, cnt = [""] * M, 1
    ans[A[0][2]] = "{:06}{:06}".format(A[0][0], cnt)
    for i in range(1, M):
        if A[i - 1][0] == A[i][0]:
            cnt += 1
        else:
            cnt = 1
        ans[A[i][2]] = "{:06}{:06}".format(A[i][0], cnt)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().split()))
    P = [[] for _ in range(N + 1)]  
    for num in range(M):  
        pref, year = tuple(map(int, input().split()))
        P[pref] += [(year, num)]
    ans = [""] * M
    P = tuple(sorted(p) for p in P)  
    for pref_idx, pref in enumerate(P):
        for city_idx, (_, num) in enumerate(pref, 1):
            x = "{:06}{:06}".format(pref_idx, city_idx)
            ans[num] = x
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().split()))
    P = [[] for _ in range(N + 1)]  
    for num in range(M):  
        pref, year = tuple(map(int, input().split()))
        P[pref] += [(year, num)]
    ans = [""] * M
    P = (sorted(p) for p in P)  
    for pref_idx, pref in enumerate(P):
        for city_idx, (_, num) in enumerate(pref, 1):
            x = "{:06}{:06}".format(pref_idx, city_idx)
            ans[num] = x
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().split()))
    P = [[] for _ in range(N + 1)]  
    for num in range(M):  
        pref, year = tuple(map(int, input().split()))
        P[pref] += [(year, num)]
    ans = [""] * M
    P = [sorted(p) for p in P]  
    for pref_idx, pref in enumerate(P):
        for city_idx, (_, num) in enumerate(pref, 1):
            x = "{:06}{:06}".format(pref_idx, city_idx)
            ans[num] = x
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int, input().split())
contrys = sorted([{"i":i, "city":list(map(int, input().split()))} for i in range(m)], key=lambda x:x["city"])

i=1
prefecture=1
for c in contrys:
    if prefecture != c["city"][0]:
        i=1
    c.setdefault("id", str(c["city"][0]).zfill(6)+str(i).zfill(6))
    prefecture=c["city"][0]
    i+=1

for c in sorted(contrys, key=lambda x: x["i"]):
    print(c["id"])

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    P = [[] for _ in range(N + 1)]  
    for num in range(M):
        pref, year = map(int, input().split())
        P[pref] += [(year, num)]
    ans = []
    P = [sorted(p) for p in P]  
    for pref_idx, pref in enumerate(P):
        for city_idx, (_, num) in enumerate(pref, 1):
            x = "{:06}{:06}".format(pref_idx, city_idx)
            ans += [(num, x)]
    print(*[i[1] for i in sorted(ans)], sep="\n")  

if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ans, A, cnt = [""] * M, [], 1
    for i in range(M):
        p, y = map(int, input().split())
        A += [(p, y, i)]
    A.sort()

    ans[A[0][2]] = "{:06}{:06}".format(A[0][0], cnt)
    for i in range(1, M):
        if A[i - 1][0] == A[i][0]:
            cnt += 1
        else:
            cnt = 1
        ans[A[i][2]] = "{:06}{:06}".format(A[i][0], cnt)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

L = sorted(L)

reset = 0
count = 0
ans = []
for i in range(M):
    if L[i][0] != reset:
        reset = L[i][0]
        count = 1
    else:
        count += 1
    
    ans.append([L[i][2], str(reset).zfill(6) + str(count).zfill(6)])

ans = sorted(ans)

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

Solution (Python):

n,m=map(int,input().split())
L={}
lp=[list() for _ in range(n)]
for cn in range(m):
  p,y=map(int,input().split())
  lp[p-1].append([y,cn])
for pre in range(n):
  k=len(lp[pre])
  if k>0:
    sd=lp[pre]
    asd=sorted(sd)
    for d in range(k):
      cn=asd[d][1]
      ans="0"*(6-len(str(pre+1)))+str(pre+1)+"0"*(6-len(str(d+1)))+str(d+1)
      L[cn]=ans
for h in range(m):
  print(L[h])

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().split()))
    P = [[] for _ in range(N + 1)]  
    for num in range(M):
        pref, year = tuple(map(int, input().split()))
        P[pref] += [(year, num)]
    ans = []
    P = [sorted(p) for p in P]
    for pref_idx, pref in enumerate(P[1:], 1):
        if pref:
            for city_idx, (_, num) in enumerate(pref, 1):
                x = "{:06}{:06}".format(pref_idx, city_idx)
                ans += [(num, x)]
    print(*[i[1] for i in sorted(ans)], sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    P = [[] for _ in range(N + 1)]  
    for num in range(M):
        pref, year = map(int, input().split())
        P[pref] += [(year, num)]
    ans, P = [], [sorted(p) for p in P]
    for pref_idx, pref in enumerate(P[1:], 1):
        if pref:
            for city_idx, (_, num) in enumerate(pref, 1):
                x = "{:06}{:06}".format(pref_idx, city_idx)
                ans += [(num, x)]
    print(*[i[1] for i in sorted(ans)], sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
t=[[] for _ in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    t[p-1].append((y,i))
ans=[""]*m
for i,j in enumerate(t,1):
    j.sort()
    for k,(j,l) in enumerate(j,1):
        ans[l]=str(i).zfill(6)+str(k).zfill(6)
print("\n".join(ans))

Solution (Python):
N,M= list(map(int, input().split()))
li=[list(map(int,input().split())) for _ in range(M)]
lisorted=sorted(li)
dic={}
memo=0
for i in lisorted:
    if memo!=i[0]:
        check=1
        dic[i[1]]="{0:06d}".format(i[0])+"{0:06d}".format(check)
        memo=i[0]
    else:
        check+=1
        dic[i[1]]="{0:06d}".format(i[0])+"{0:06d}".format(check)
for i in li:
    print(dic[i[1]])

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
lst = [[] for _ in range(n)]
py = [LI() for _ in range(m)]
for i in range(m):
    p,y = py[i]
    lst[p-1].append(y)
for i in lst:
    i.sort()
for i in range(m):
    p,y = py[i]
    s1 = '00000' + str(p)
    s2 = '00000' + str(bisect.bisect_right(lst[p-1],y))
    ans = s1[-6:] + s2[-6:]
    print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
lst = [[] for _ in range(n)]
py = [LI() for _ in range(m)]
for i in range(m):
    p,y = py[i]
    lst[p-1].append(y)
for i in lst:
    i.sort()
for i in range(m):
    p,y = py[i]
    s1 = '00000' + str(p)
    s2 = '00000' + str(bisect.bisect_right(lst[p-1],y))
    ans = s1[-6:] + s2[-6:]
    print(ans)

Solution (Python):
import heapq
import sys

N, M = map(int, input().split())
clist = []
HQ = [[] for _ in range(N)]
for i in range(M):
    p, y = map(int, input().split())
    clist.append((p, y))
    heapq.heappush(HQ[p - 1], y)

cmap = {}
for p, q in enumerate(HQ):
    cnt = 0
    for i in range(len(q)):
        y = heapq.heappop(q)
        cmap[str(p) + '_' + str(y)] = i + 1

for p, y in clist:
    idx = cmap[str(p - 1) + '_' + str(y)]
    print('{0:06d}'.format(p) + '{0:06d}'.format(idx))

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

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

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

ans = [None]*M

for i,y in enumerate(prefec):
  y.sort()
  for k ,(y,j) in enumerate(y):
    ans[j] = "%06d%06d" %(i+1,k+1)
    
print(*ans,end ='\n')

Solution (Python):
def c_id():
    from collections import defaultdict
    N, M = map(int, input().split())
    City = [[s] + [int(i) for i in input().split()] for s in range(M)]

    
    city_dict = defaultdict(list)
    for k, p, y in City:
        city_dict[p].append([k, p, y])
    for p in city_dict.keys():
        city_dict[p].sort(key=lambda x: x[2])
        for i in range(len(city_dict[p])):
            city_dict[p][i][2] = i + 1

    
    ans = sorted([e for v in city_dict.values() for e in v])
    return '\n'.join(['{0:06d}{1:06d}'.format(p, num) for _, p, num in ans])  

print(c_id())

Solution (Python):
n, m = map(int, input().split())
l = []
k = ['_'] * m
x = [1] * (n+1)
for i in range(m):
    a, b = map(int, input().split())
    l.append([i, a, b])
y = sorted(l, key=lambda c: c[2])
for i in y:
    k[i[0]] = str(i[1]).zfill(6) + str(x[i[1]]).zfill(6)
    x[i[1]] += 1
for i in k:
    print(i)

Solution (Python):
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if len(ps) == 0:
        return next(args)
    elif type(ps[0]) is list:
        return [input(*ps[0][0]) for _ in range(ps[0][1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def main():
    N, M = input(int, int)

    ps = dd(list)
    for i in range(M):
        p, y = input(int, int)
        ps[p].append((y, i))
    ans = [None] * M
    for k, v in ps.items():
        v.sort()
        for i, c in enumerate(v, start=1):
            ans[c[1]] = (k, i)
    for v in ans:
        print("{:06d}{:06d}".format(v[0], v[1]))

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

n,m=map(int,input().split())
l=[]
for i in range(m):
    p,y=map(int,input().split())
    heappush(l,[p,y,i])
ans=[0]*m
k=l[0][0]
i=1
for _ in range(m):
    L=heappop(l)
    if L[0]!=k:
        i=1
        k=L[0]
    ans[L[2]]=str(L[0]).rjust(6,'0')+str(i).rjust(6,'0')
    i+=1
print(*ans,sep='\n')

Solution (Python):
N, M = map(int, input().split())
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort(key = lambda x: x[1])
PY.sort(key = lambda x: x[0])

ans_lst = []
x = 1
tmp_p = None
for p, y, i in PY:
    if p == tmp_p: 
        ans_lst.append([p, x, i])
        x += 1
    else:
        ans_lst.append([p, 1, i])
        tmp_p = p
        x = 2

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



for p, x, i in ans_lst:
    ans_p = str('000000') + str(p)
    ans_x = str('000000') + str(x)
    
    
    print (ans_p[-6:], ans_x[-6:], sep = '')

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

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



ans = [0] * M

for P, l in enumerate(PList):
    if not l:
        continue
    l.sort()
    for j, (Y, i) in enumerate(l):
        ans[i] = "{:06d}{:06d}".format(P, j+1)



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

Solution (Python):
from bisect import *

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
D = {}
for i in range(M) :
    p, y = L[i]
    if p not in D :
        D[p] = [y]
    else :
        D[p].append(y)

for p in D :
    D[p] = sorted(D[p])

for i in range(M) :
    p, y = L[i]
    ind = bisect_left(D[p], y)
    res = str(p).zfill(6) + str(ind+1).zfill(6)
    print(res)

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

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

pref = [[0] for i in range(N+1)]
import collections
q = collections.deque()
 
for i in range(M):
    p,y = map(int, input().split())
    pref[p].append(y)
    q.append((p,y))
for p in pref:
    p.sort()

import bisect
for p,y in q:
    print("%06d%06d" %(p, bisect.bisect_left(pref[p], y)))

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]+=[y]
for x,y in p:
  z=bisect.bisect(a[x],y)
  print("%06d%06d"%(x,z))

Solution (Python):
import collections
import bisect

n,m=map(int,input().split())
a=collections.defaultdict(list)
p=[[int(j) for j in input().split()] for i in range(m)]
for x,y in sorted(p):
  a[x]+=[y]
for x,y in p:
  z=bisect.bisect(a[x],y)
  print("%06d%06d"%(x,z))

Solution (Python):
n,m=map(int,input().split())
cnt=[[] for _ in range(n+1)]
for i in range(m):
    p,y=map(int,input().split())
    cnt[p].append((y,i))
buf=[None]*m
for p,l in enumerate(cnt):
    if not l:
        continue
    l.sort()
    for j, (y,i) in enumerate(l):
        buf[i]="{:06d}{:06d}".format(p,j+1)
print("\n".join(buf))

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
city_dict = defaultdict(list)

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



result_list = []
for k, v in city_dict.items():
    v.sort(key=lambda x: x[1])
    mae = ("00000" + str(k))[-6:]
    
    for i,tup in enumerate(v):
        ato= ("00000" + str(i+1))[-6:]
        result_list.append((tup[0], mae + ato))
result_list.sort(key=lambda x: x[0])

for i,j in result_list:
    print(j)

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]+=[y]
for x,y in p:
    z=bisect.bisect(a[x],y)
    print("%06d%06d"%(x,z))

Solution (Python):
import sys

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    P = [0] * (N + 1)
    C = [0] * M

    for m in range(M):
        p, y = map(int, input().split())
        C[m] = [m, p, y, 0]
    C.sort(key=lambda x :x[2])

    for c in C:
        P[c[1]] += 1
        c[3] = P[c[1]]
    C.sort(key=lambda x :x[0])

    for c in C:
        print("{}{}".format(str(c[1]).zfill(6), str(c[3]).zfill(6)))

Solution (Python):
def resolve():
    N,M=map(int,input().split())
    Y = [list(map(int,input().split()))+[0] for i in range(M)]
    Y2 = sorted(Y)
    index=0
    for i in Y2:
        if i[0]!=index:
            x=1
        else:
            x+=1
        index=i[0]
        i[2] = x
    for i in Y:
        print(str(i[0]).zfill(6)+str(i[2]).zfill(6))
resolve()

Solution (Python):
N,M=map(int, input().split())
py=[list(map(int, input().split())) for _ in range(M)]
cnt=[0]*(N+1)
ids={}
for p,y in sorted(py, key=lambda x: x[1]):
	cnt[p] += 1
	ids[y] = "%06d%06d" % (p, cnt[p])
for _,y in py:
	print(ids[y])

Solution (Python):
n,m = map(int,input().split())
inl = [[i] + list(map(int,input().split())) for i in range(m)]
inl = sorted(inl,key=lambda x:x[2])
inl = sorted(inl,key=lambda x:x[1])
cnt = 1
for i in range(m):
    a = str(inl[i][1]).rjust(6,"0")
    b = str(cnt).rjust(6,"0")
    cnt +=1
    if i !=m-1 and inl[i][1] != inl[i+1][1]:
        cnt = 1
    inl[i][1] = a
    inl[i][2] = b
inl = sorted(inl,key=lambda x:x[0])
for i in range(m):
    print(str(inl[i][1])+str(inl[i][2]))

Solution (Python):
n, m = [ int(v) for v in input().split() ]
city_list = [ [] for i in range(n+1) ]

for i in range(m):
    p, y = [ int(v) for v in input().split() ]
    city_list[p].append((y,i))
city_list = [ sorted(i) for i in city_list ]

def numbering(a,b):
    a, b = str(a), str(b)
    return a.zfill(6) + b.zfill(6)

ans_list = []
for i, w in enumerate(city_list):
    for j, v in enumerate(w,1):
        ans_list.append((v[1], numbering(i, j)))

for i in sorted(ans_list):
    print(i[1])

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

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

ans = [0] * m
temp = 1

for i in range(len(L)):
    kami = str(L[i][1]).rjust(6, "0")
    shimo = str(temp).rjust(6, "0")
    ans[L[i][0]] = kami+shimo

    if i < (m-1) and L[i][1] != L[i+1][1]:
        temp = 1
    else:
        temp += 1

for a in ans:
    print(a)

Solution (Python):
import math
import sys
from itertools import accumulate
from functools import reduce
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""

a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654


char_list = list("abcd") 



    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())
    = [list(map(str,list(sys.stdin.readline().split()))) for i in range(h)]


    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  
"""

if __name__ == "__main__":
    import collections
    import bisect
    n,m= map(int, sys.stdin.readline().split())
    c = [list(map(int,list(sys.stdin.readline().split()))) for i in range(m)]
    a = collections.defaultdict(list)
    for x,y in sorted(c):
        a[x] += [y]
    for x,y in c:
        z = bisect.bisect(a[x],y)
        print("%06d%06d"%(x,z))

Solution (Python):
def solve():
    n, m = map(int, input().split())
    py = list(list(map(int, input().split())) for _ in range(m))
    py_with_key = sorted([(idx, pyi) for idx, pyi in enumerate(py)], key=lambda x: x[1])
    pref_no = 1
    cnt = 0
    ids = []
    for idx, p_y in py_with_key:
        if pref_no == p_y[0]:
            cnt += 1
        else:
            pref_no = p_y[0]
            cnt = 1
        city_id = '{0:06d}{1:06d}'.format(p_y[0], cnt)
        ids.append((idx, city_id))
    return "\n".join([x[1] for x in sorted(ids, key=lambda x: x[0])])


if __name__ == "__main__":
    print(solve())

Solution (Python):
import bisect
import heapq
n,m=map(int,input().split())
py_i=[[int(x) for x in input().split()] for _ in range(m)]
y_p=[[] for i in range(n+1)]
for x,y in sorted(py_i):
    
    y_p[x].append(y)
for x,y in py_i:
    z=bisect.bisect_right(y_p[x],y)
    print("%06d"%x+"%06d"%z)

Solution (Python):
from collections import defaultdict
import bisect
N, M = map(int, input().split())
P = [[int(i) for i in input().split()] for _ in range(M)]
D = defaultdict(list)

for p, y in sorted(P):
  D[p] += [y]
  
for p, y in P:
  z = bisect.bisect(D[p], y)
  print ("%06d%06d"%(p, z))

Solution (Python):
n,m=map(int,input().split())
py=[[-1,-1,-1]]
for i in range(m):
	x,y=map(int,input().split())
	py.append([x,y,i])
py.sort()
x=[]
cnt=1
for i in range(1,m+1):
	d=""
	if py[i-1][0]==py[i][0]:
		cnt+=1
	else:
		cnt=1
	d+="0"*+(6-len(str(py[i][0])))+str(py[i][0])
	d+="0"*(6-len(str(cnt)))+str(cnt)
	x.append([d,py[i][2]])
x.sort(key=lambda x:x[1])
for i in range(m):
	print(x[i][0])

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

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

l.sort()  


c = l[0][0]
x = 0

new_l = [[0, 0] for _ in range(m)]

for j in range(m):
  if l[j][0] != c:
    x = 1
    c = l[j][0]
  else:
    x += 1
  new_l[j][0] = str(l[j][0]).zfill(6)+str(x).zfill(6)
  new_l[j][1] = l[j][2]

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

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

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

X.sort()


count = [0] * (N+1)
ans_list = [[] for _ in range(M)]

for i in range(len(X)):
    count[X[i][1]] += 1
    tmp = ('000000'+ str(X[i][1]))[-6:] + ('000000'+ str(count[X[i][1]]))[-6:]
    ans_list[X[i][2]] = tmp

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

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


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

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

for i in range(n):
        p[i].sort()
ans=[""]*m
for i in range(n):
        for j in range(len(p[i])):
                ans[p[i][j][1]]=str(i+1).zfill(6)+str(j+1).zfill(6)

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

Solution (Python):
import collections
import bisect


N, M = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(M)]
a = collections.defaultdict(list)
for x, y in sorted(P):
    a[x] += [y]
for x, y in P:
    idx = bisect.bisect(a[x], y)
    print(str(x).zfill(6), str(idx).zfill(6), sep='')

Solution (Python):
N, M = [int(nm) for nm in input().split()]
PY = []
for m in range(M):
  PY.append([int(py) for py in input().split()] + [m])

PY.sort(key=lambda x: (x[0], x[1]))
p_ID = PY[0][0]
y_ID = 0
ID = []
for m in range(M):
  p, y, i = PY[m]
  if p == p_ID:
    y_ID += 1
  else: 
    p_ID = p
    y_ID = 1
  iidd = "0"*(6-len(str(p_ID))) + str(p_ID) + "0"*(6-len(str(y_ID))) + str(y_ID)
  ID.append([iidd, i])

ID.sort(key=lambda x: x[1])
for m in range(M):
  print(ID[m][0])

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



a=[0]*n
ans=[""]*m
for y,p,i in x:  	
    a[p-1]+=1
    
    ans[i]=str(p).rjust(6,"0")+str(a[p-1]).rjust(6,"0")
for i in ans:
    print(i)

Solution (Python):
n,m = map(int, input().split())
x=[]
for i in range(m):
    p,y=map(int,input().split())
    x.append([y,p,i])
x.sort()
a=[0]*n
ans=[""]*m
for y,p,i in x:
    a[p-1]+=1
    ans[i]=str(p).rjust(6,"0")+str(a[p-1]).rjust(6,"0")
for i in ans:
    print(i)

Solution (Python):
import heapq
N,M = map(int,input().split())
ans = [[0,0]for i in range(M)]
cityes = [[]for i in range(N)]
for i in range(M):
    p,y = map(int,input().split())
    heapq.heappush(cityes[p-1],[y,i])
for i in range(N):
    j = 0
    while cityes[i] != []:
        j += 1
        y,n = heapq.heappop(cityes[i])
        ans[n] = [i+1,j]
for a,b in ans:
    out = str(1000000+a)[1:] + str(1000000+b)[1:]
    print(out)

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

Solution (Python):
import itertools
import collections

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

n,m=getints()

values = [getints() for _ in range(m)]

dic = collections.defaultdict(list)

for a,b in values:
    dic[a].append(b)

mp = collections.defaultdict(collections.defaultdict)

for k in dic.keys():
    dic[k] = list(sorted(dic[k]))
    for i in range(len(dic[k])):
        mp[k][dic[k][i]] = i + 1


for a,b in values:
    d = mp[a][b]
    res1 = str(a)
    while len(res1) != 6:
        res1 = "0" + res1
    res2 = str(d)
    while len(res2) != 6:
        res2 = "0" + res2
    print(res1 + res2)

Solution (Python):
n,m = map(int,input().split())
lis = [] 
ID = [0 for _ in range(m)]
cnt = [0 for _ in range(n)]

for i in range(m):
    p,y = map(int,input().split())
    lis.append([i,p,y])
lis = sorted(lis,key = lambda x:x[2])
for i in range(m):
    cnt[lis[i][1]-1] += 1 
    up = "0" * (6 - len(str(lis[i][1]))) + str(lis[i][1])
    under = "0" * (6 - len(str(cnt[lis[i][1]-1]))) + str(cnt[lis[i][1]-1])
    ID[lis[i][0]] = up + under
for i in range(m):
    print(ID[i])

Solution (Python):
from operator import itemgetter
n1, n2 = [int(i) for i in input().split()]

n3 = []

for i1 in range(n2):
    n3.append([int(i) for i in input().split()])
    n3[i1].append(i1)
    n3[i1].append(0)

n3.sort(key=itemgetter(1))

n4 = [0] * n1

for i2 in range(n2):
    n4[n3[i2][0] - 1] += 1
    n3[i2][3] = n4[n3[i2][0] - 1]

n3.sort(key=itemgetter(2))

for i3 in range(n2):
    print(str(n3[i3][0]).zfill(6) + str(n3[i3][3]).zfill(6))

Solution (Python):

import sys
import bisect

def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    
    val = [[] for i in range(N+1)]
    for pi, yi in [[P[i], Y[i]] for i in range(M)]:
        val[pi].append(yi)

    for i in val:
        i.sort()


    a = sorted([[P[i], Y[i]] for i in range(M)], key=lambda x:(x[0],x[1]))

    for p, y in [[P[i], Y[i]] for i in range(M)]:
        c_id = bisect.bisect_left(val[p], y)
        print(str(p).zfill(6)+str(c_id+1).zfill(6))
    
    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):
import bisect

n,m=map(int,input().split())
p=[]
y=[]
yd=[[] for _ in range(n+1)]
for i in range(m):
    pp,yy=map(int,input().split())
    p.append(pp)
    y.append(yy)
    yd[p[i]].append(y[i])
for i in range(n):
    yd[i+1].sort()
for i in range(m):
    x=p[i]*1000000+bisect.bisect_left(yd[p[i]],y[i])+1
    x=str(x)
    print("0"*(12-len(x))+x)

Solution (Python):
import bisect

n,m=map(int,input().split())
p=[]
y=[]
yd=[[] for _ in range(n+1)]
for i in range(m):
    pp,yy=map(int,input().split())
    p.append(pp)
    y.append(yy)
    yd[p[i]].append(y[i])
for i in range(n):
    yd[i+1].sort()
for i in range(m):
    x=p[i]*1000000+bisect.bisect_left(yd[p[i]],y[i])+1
    x=str(x)
    print("0"*(12-len(x))+x)

Solution (Python):
n , m = list(map(int,input().split()))
lll = []
iii = [0 for _ in range(m)]
ppp = [1 for _ in range(n)]
for i in range(m):
  p, y =list(map(int,input().split()))
  lll.append([i,p,y])
lll.sort(key=lambda x:x[2])
for i in range(m):
  p = lll[i][1]
  x = ppp[p-1]
  iii[lll[i][0]] = "{0:06d}".format(p) + "{0:06d}".format(x)
  ppp[p-1] += 1
for i in iii:
  print(i)

Solution (Python):
from collections import defaultdict
N, M = list(map(int, input().split()))
YP = []
for _ in range(M):
    p, y = list(map(int, input().split()))
    YP.append([y, p])

sortedYP = sorted(YP)

Pcount = defaultdict(int)
ansYear = {}

for m in range(M):
    y, p = sortedYP[m]
    Pcount[p] += 1
    ansYear[y] = Pcount[p]

for m in range(M):
    y, p = YP[m]
    print(str(p).zfill(6) + str(ansYear[y]).zfill(6))

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

_number = []
P = []
Y = []
yp = [[] for i in range(N+1)]
_yp = []

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



_l_yp = len(yp)

for i in range(_l_yp):
    yp[i].sort()


ans_yp = [[] for i in range(M)]

for i in range(_l_yp):
    nga_yp = len(yp[i])

    for j in range(nga_yp):
    
    
       ans_yp[yp[i][j][1]].append(i)
       ans_yp[yp[i][j][1]].append(j+1)


__len = len(ans_yp)

for i in range(__len):
    buff = ''
    for d in range(2):
        ans = ''
        for j in range((6-len(str(ans_yp[i][d])))):
            ans += '0'

        buff += ans + str(ans_yp[i][d])

    print(buff)

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

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

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



now_pref = city_info[0][1]

tmp = 0
for i in range(M):
    if city_info[i][1] == now_pref:
        tmp += 1
        city_info[i][3] = tmp
    else:
        tmp = 1
        city_info[i][3] = tmp
        now_pref = city_info[i][1]

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




for i in range(M):
    str_p = str(city_info[i][1])
    str_zyunban = str(city_info[i][3])

    lack_p = 6-len(str_p)
    str_p = '0'*lack_p + str_p

    lack_zyunban = 6-len(str_zyunban)
    str_zyunban = '0'*lack_zyunban + str_zyunban

    print(str_p+str_zyunban)

Solution (Python):
n, m = map(int, input().split())
dict_ = {i:tuple(map(int, input().split())) for i in range(m)}

sorted_dict = sorted(dict_.items(), key=lambda x: x[1])

res = {}
tmp = ''
cnt = 0
for item in sorted_dict:
    if item[1][0] == tmp:
        cnt += 1
    else:
        tmp = item[1][0]
        cnt = 1
    res[item[0]] = str(item[1][0]).zfill(6) + str(cnt).zfill(6)

for i in sorted(res.items()):
    print(i[1])

Solution (Python):
N,M = map(int,input().split())
h = [list(map(int, input().split()))for i in range(M)]
for i in range(M):
    h[i].append(i)
h = sorted(h,key=lambda h:(h[0],h[1]))
k = 0
p = h[0][0]
for i in range(M):
    if h[i][0] == p:
        h[i].append(str(p).zfill(6)+str(k+1).zfill(6))
        k+=1
    else:
        p = h[i][0]
        k = 0
        h[i].append(str(p).zfill(6) + str(k + 1).zfill(6))
        k += 1

h = sorted(h,key=lambda h:h[2])

for i in range(M):
    print(h[i][3])