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
import math
from fractions import gcd
import bisect





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)

big_prime = 1000000007

"""


 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())


 =  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(N)]
"""




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

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

d = {}

for o in org:
    d.setdefault(o[0], [])
    d[o[0]].append(o[1])

for l in d.values():
    l.sort()

for o in org:
    order = bisect.bisect_left(d[o[0]],o[1]) + 1
    print(str(o[0]).zfill(6) + str(order).zfill(6))

Solution (Python):
def main():
  from sys import stdin
  from bisect import bisect_left
  readline = stdin.readline
  n, m = map(int, readline().split())
  data = [list(map(int, readline().split())) for _ in range(m)]
  t = [[] for _ in range(n)]
  for p, y in data:
    t[p - 1].append(y)
  for i in range(n):
    t[i].sort()
  for p, y in data:
    nth = bisect_left(t[p - 1], y) + 1
    print("%06d%06d" % (p, nth))
main()

Solution (Python):
from bisect import bisect_left
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
t = [[] for _ in range(n)]
for p, y in data:
  t[p - 1].append(y)
for i in range(n):
  t[i].sort()
for p, y in data:
  nth = bisect_left(t[p - 1], y) + 1
  print("%06d%06d" % (p, nth))

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(m):
  p,y=map(int,input().split())
  l.append([y,i,p])
l=sorted(l)
l1=[0 for i in range(n+1)] 
l2=[[] for i in range(m)] 
for i in range(m):
  l1[l[i][2]]+=1
  l2[l[i][1]]=[l1[l[i][2]],l[i][2]]
for i in range(m):
  w=""
  w+="0"*(6-len(str(l2[i][1])))+str(l2[i][1])+"0"*(6-len(str(l2[i][0])))+str(l2[i][0])
  print(w)

Solution (Python):
import sys
import math
from operator import itemgetter

n,m = map(int, input().split())
city = [0] * m
dict = {}

for i in range(m):
    p,y = map(int, input().split())
    city[i] = [i,p,y,0]
    dict.setdefault(p,1)
city = sorted(city,key=itemgetter(2))

for j in range(m):
    city[j][3] = format(city[j][1],'06') + format(dict[city[j][1]],'06')
    dict[city[j][1]] = dict[city[j][1]] + 1

city = sorted(city,key=itemgetter(0))

for k in range(m):
    print(city[k][3])

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N, M = map(int, input().split())
src = [tuple(map(int, input().split())) for _ in range(M)]



X = [ [] for _ in range(N+1) ]

for i, (p, y) in enumerate(src):
    X[p].append((y, i))
for c in X:
    c.sort()



ans = [None] * M
for p in range(len(X)):
    
    for i,(_,j) in enumerate(X[p]):
        s = str(p).zfill(6) + str(i+1).zfill(6)
        ans[j] = s

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

Solution (Python):
from operator import itemgetter
n, m = map(int, input().split())
py = []
for i in range(m):
    a, b = map(int, input().split())
    py.append([a, b, i])
py.sort()
py[0][1] = 1
for i in range(m-1):  
    if py[i+1][0] == py[i][0]:
        py[i+1][1] = py[i][1] + 1
    else:
        py[i+1][1] = 1
py.sort(key=itemgetter(2))

for i in range(m):
    a, b = str(py[i][0]), str(py[i][1])
    print(a.zfill(6)+b.zfill(6))

Solution (Python):
N,M=[int(s) for s in input().split()]
lst=[]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  lst.append([a,b,i])
lst.sort()
city=0
count=1
for e in lst :
  if e[0]>city :
    city=e[0]
    count=1
  e[0]=10**12+e[0]*10**6+count
  count=count+1
lst=sorted(lst,key=lambda e:e[2])
for e in lst :
  print(str(e[0])[1:])

Solution (Python):

from collections import deque
n,m=map(int,input().split())
s=[]
for i in range(m):
    p,y=map(int,input().split())
    s.append([y,p,i+1])
s=sorted(s)
s=deque(s)
s.appendleft(0)
t=[1]*(n+1)
ID=[0]*(m+1)
for i in range(1,m+1):
    ID[s[i][2]]=str(s[i][1]*(10**6)+t[s[i][1]]).zfill(12)
    t[s[i][1]]+=1
for i in range(1,m+1):
    print(ID[i])

Solution (Python):

from collections import deque
n,m=map(int,input().split())
s=[]
for i in range(m):
    p,y=map(int,input().split())
    s.append([y,p,i+1])
s=sorted(s)
s=deque(s)
s.appendleft(0)
t=[1]*(n+1)
ID=[0]*(m+1)
for i in range(1,m+1):
    ID[s[i][2]]=str(s[i][1]*(10**6)+t[s[i][1]]).zfill(12)
    t[s[i][1]]+=1
for i in range(1,m+1):
    print(ID[i])

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):
n, m = map(int, input().split())
py = []
for _ in range(m):
  py.append(list(map(int,input().split())) + [0])

sortPy = sorted(py, key = lambda x : (x[0], x[1]))
 
d = {}
for i, (p, y, n) in enumerate(sortPy):
  if p in d:
    d[p] += 1
  else:
    d[p] = 1
  sortPy[i][2] = d[p]

for p, y, n in py:
  print(str(p).zfill(6) + str(n).zfill(6))

Solution (Python):
n, m = map(int, input().split())
py = [list(map(int, (input() + " 0 " + str(i)).split())) for i in range(m)]
py = sorted(py, key=lambda x: (x[0], x[1]))
d = {}
for i, v in enumerate(py):
    if v[0] not in d:
        d[v[0]] = 1
    else:
        d[v[0]] += 1
    v[2] = d[v[0]]
py = sorted(py, key=lambda x: x[3])
for i in py:
    print(("000000" + str(i[0]))[-6:] + ("000000" + str(i[2]))[-6:])

Solution (Python):



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

for _ in range(m):
    p, y = list(map(int, input().split()))
    py_list.append((p, y))

sorted_py_list = sorted(py_list, key=lambda x: (x[0], x[1]))

p_no = sorted_py_list[0][0]
y_index = 1
no_dict = {}

for i, py in enumerate(sorted_py_list):
    p, y = py

    if p != p_no:
        p_no = p
        y_index = 1

    no = str(p).zfill(6) + str(y_index).zfill(6)
    no_dict[(p, y)] = no
    y_index += 1

print_list = []

for p, y in py_list:
    print_list.append(no_dict[(p, y)])

ans = '\n'.join(print_list)
print(ans)

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):
N, M = map(int, input().split())
items = []
for i in range(M):
    p, y = map(int, input().split())
    items.append((p, y, i))

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

ans = {}

ken = -1
cnt = 1
for item in items:
    if item[0] != ken:
        cnt = 1
        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6)
        ken = item[0]
    else:
        cnt += 1
        ans[item[2]] = str(item[0]).zfill(6) + str(cnt).zfill(6)

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

Solution (Python):
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

n, m = an()
py = []
for _ in range(m):
  py.append(list(an()) + [0])

sortPy = sorted(py, key = lambda x : (x[0], x[1]))

d = {}
for i, (p, y, n) in enumerate(sortPy):
  if p in d:
    d[p] += 1
  else:
    d[p] = 1
  sortPy[i][2] = d[p]

for p, y, n in py:
  print(str(p).zfill(6) + str(n).zfill(6))

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

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

    e.sort(key=lambda x : (x[1],x[2]))
    cnt = 1
    for i in range(M):
        if i == 0:
            e[i][1] = str(e[i][1]).zfill(6)
            e[i][2] = str(cnt).zfill(6)
            cnt += 1
        if int(e[i-1][1]) == e[i][1]:
            cnt += 1
            e[i][1] = str(e[i][1]).zfill(6)
            e[i][2] = str(cnt).zfill(6)
        else:
            cnt = 1
            e[i][1] = str(e[i][1]).zfill(6)
            e[i][2] = str(cnt).zfill(6)

    ans = sorted(e)
    for i,j,k in ans:
        print(j+k)

main()

Solution (Python):



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

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

flag = -1
count = 1
for a in arr:
    if a[1] != flag:
        flag = a[1]
        count = 1
    a[2] = "%06d" % count
    a[1] = "%06d" % a[1]
    count += 1
arr = list(sorted(arr, key=lambda x: x[0]))
for a in arr:
    print("{}{}".format(a[1], a[2]))

Solution (Python):
"""
2 3
1 32
2 63
1 12

000001000002
000002000001
000001000001



2 3
2 55
2 77
2 99

000002000001
000002000002
000002000003
"""


first = list(map(int, input().split()))
ken_shi_dict = {}
c = 0
for i in range(first[1]):
    c += 1
    ken_year = input().split()
    ken = ken_year[0]
    year = ken_year[1]
    if ken in ken_shi_dict:
        ken_shi_dict[ken].append([year, c])
    else:
        ken_shi_dict[ken] = [[year, c]]

answer_dict = {}
sorted_ken = sorted(ken_shi_dict.keys())
for i in sorted_ken:
    count = 1
    ken_number = str(i).zfill(6)
    ken_shi_dict[i].sort(key=lambda x: int(x[0]))
    for j in ken_shi_dict[i]:
        year_number = str(count).zfill(6)
        count += 1
        print_str = ken_number + year_number
        answer_dict[j[1]] = print_str

for i in sorted(answer_dict.keys()):
    print(answer_dict[i])

Solution (Python):
from collections import defaultdict

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

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

d = defaultdict(int)
b = dict()
for p, y in sorted(years, key=lambda x: x[1]):
    d[p] += 1
    b[y] = '{:06d}{:06d}'.format(p, d[p])

for p, y in years:
    print(b[y])

Solution (Python):
from collections import defaultdict
n,m = map(int,input().split())
d = defaultdict(list)
for i in range(m):
  p,y = map(str,input().split())
  p = '0' * (6-len(p)) + p
  d[p].append([int(y),i])
ans = [0] * m
for p in d:
  c = 0
  for t in sorted(d[p]):
    c += 1
    ans[t[1]] = p + '0' * (6-len(str(c))) + str(c)
print('\n'.join(ans))

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
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



N,M = II()
P,Y = Line(M)

a = defaultdict(list)
for i in range(M):
    a[P[i]].append([Y[i],i])

for p in a.keys():
    a[p].sort(key = lambda x:x[0])

b = []
for p in a.keys():
    for i,y in enumerate(a[p]):
        b.append([str(p).zfill(6)+str(i+1).zfill(6),y[1]])

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

Solution (Python):

"""
N, M = 10000, 10000
C = [[] for _ in range(N+1)]
for i in range(M):
    p, y = N-i, i*4+M
    C[p].append((y, i))


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



R = [[] for _ in range(M)]
for p, P in enumerate(C):
    x = 1
    for y, i in sorted(P):
        R[i].append((p, x))
        x += 1

for px in R:
    print("{:06d}{:06d}".format(*px[0]))

Solution (Python):
N,M = map(int,input().split())
PrefDB = [ [i] + [int(x) for x in input().split()] for i in range(M)]
PrefDB.sort(key=lambda x:(x[1],x[2]))
counter = 1
pred = 0
for i in range(M):
    if pred != PrefDB[i][1]:
        counter = 1
    PrefDB[i].append(str(1000000000000 + PrefDB[i][1]*1000000 + counter)[1:])
    pred = PrefDB[i][1]
    counter += 1
PrefDB.sort(key=lambda x:x[0])
for i in range(M):
    print(PrefDB[i][-1])

Solution (Python):
n, m = map(int, input().split())
py_array = [[int(x) for x in input().split()] for y in range(m)]
py_dict = {x: y for x, y in enumerate(py_array, 1)}
py = sorted(py_dict.items(), key=lambda x: x[1][1])
ans = {}
now = min([x[0] for x in py_array])
index = 0
index_array = {x: 0 for x in [x[0] for x in py_array]}
for key, value in py:
    index_array[value[0]] += 1
    index = index_array[value[0]]
    ken = str(value[0])
    si = str(index)
    ans[key] = ken.zfill(6) + si.zfill(6)
    now = value[0]
for key, value in ans.items():
    print(value)

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

for i in range(len(pLst)):
    pLst[i].append(i)
nLst = [''] * N

for i in range(N):
    nLst[i] = str(i + 1).zfill(6)
tLst = sorted(pLst, key=lambda x: (x[0], x[1]))
ansLst = [''] * M
tmp = nLst[tLst[0][0] - 1]
index = 1
for i in range(M):
    if tmp == nLst[tLst[i][0] - 1]:
        ansLst[tLst[i][2]] = nLst[tLst[i][0] - 1] + str(index).zfill(6)
        index += 1
    else:
        index = 1
        tmp = nLst[tLst[i][0] - 1]
        ansLst[tLst[i][2]] = nLst[tLst[i][0] - 1] + str(index).zfill(6)
        index += 1

for i in ansLst:
    print(i)

Solution (Python):
import bisect
def index(alist, x):
    i = bisect.bisect_left(alist, x)
    if i != len(alist) and alist[i] == x:
        return i
    raise ValueError

n, m = map(int, input().split())
p, y = [0] * m, [0] * m
year_list = [[] for _ in range(n)]
for i in range(m):
    p[i], y[i] = map(int, input().split())
    year_list[p[i] - 1].append(y[i])
for j in range(n):
    year_list[j].sort()
for i in range(m):
    x = index(year_list[p[i] - 1], y[i]) + 1
    print(str(p[i]).zfill(6) + str(x).zfill(6))

Solution (Python):
N,M = map(int,input().split())
lst = [None]*(M+1)
pre_count = 1
pre_current = ''
lst[0] = ['000000',0,0]
for i in range(1,M+1):
  lst[i] = list(map(int,input().split()))
  lst[i].append(i)
for k in range(1,M+1):
  lst[k][0] = str(lst[k][0])
  lst[k][0] = lst[k][0].zfill(6)
lst.sort(key = lambda x:x[1])
lst.sort(key = lambda x:x[0])
for j in range(1,M+1):
  if lst[j][0] == lst[j-1][0]:
    pre_count += 1
    lst[j].append(str(pre_count).zfill(6))
  else:
    pre_count = 1
    lst[j].append(str(pre_count).zfill(6))
lst.sort(key = lambda x:x[2])
for x in range(1,M+1):
  print(lst[x][0]+lst[x][3])

Solution (Python):
from bisect import bisect_left

n, m = map(int, input().split())
py = [tuple(map(int, input().split())) for _ in range(m)]
pym = {}
for i, (p, y) in enumerate(py):
    if p not in pym:
        pym[p] = []
    pym[p].append(y)

for p, yy in pym.items():
    yy.sort()

for (p, y) in py:
    ps = ('000000' + str(p))[-6:]
    ys = ('000000' + str(bisect_left(pym[p], y) + 1))[-6:]
    print(ps+ys)

Solution (Python):
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    N, M = map(int, input().split())
    si = []

    for i in range(M):
        tmp = [int(j) for j in input().split()]
        tmp.append(i)
        tmp.append(0)
        si.append(tmp)

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

    count = 1
    num = 1
    for i, s in enumerate(si):
        if num == s[0]:
            si[i][3] = count
            count += 1
        else:
            num = s[0]
            si[i][3] = 1
            count = 2

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

    for s in si:
        print(str(s[0]).zfill(6)+str(s[3]).zfill(6))


if __name__ == '__main__':
    main()

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

lis2 = []
for j in range(len(lis)):
  l = lis[j]
  if l:
    l.sort(key=lambda x: x[1])
    cnt = 1
    for city in l:
      city.append("{:06}{:06}".format(j+1, cnt))
      cnt += 1
      lis2.append(city)

lis2.sort(key=lambda x: x[0])
for l2 in lis2:
  print(l2[2])

Solution (Python):
pre_n, city_n = map(int, input().split())
cities = [list(map(int, input().split())) for x in range(city_n)]

history = {}

A = {}

for x in sorted(cities):
    pref = str(x[0])
    if pref not in history:
        history[pref] = '1'

    A.setdefault(str(x), '0'*(6-len(pref)) + pref + '0'*(6-len(history[pref])) + history[pref])

    history[pref] = str(int(history[pref]) + 1)

for x in cities:
    print(A[str(x)])

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


def main():
    N, M = map(int, input().split())
    cities = []

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

    city_nums = [0]*(N+1)
    ids = []
    for city in sorted(cities, key=lambda x: x[2]):
        city_nums[city[1]] += 1
        
        s = '{0:0>6}{1:0>6}'.format(city[1], city_nums[city[1]])
        ids.append((city[0], s))

    for _, num in sorted(ids, key=lambda x: x[0]):
        print(num)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    cities = dict()
    for i in range(M):
        P, Y = map(int, input().split())
        if P not in cities:
            cities[P] = [[Y, i]]
        else:
            cities[P].append([Y, i])

    ans = [0 for _ in range(M)]
    for P in cities:
        cities[P] = sorted(cities[P])
        id = 1
        for _, j in cities[P]:
            ans[j] = "0"*(6-len(str(P)))+str(P)+ "0"*(6-len(str(id))) + str(id)
            id += 1
    for s in ans:
        print(s)

if __name__ == '__main__':
    main()

Solution (Python):
import collections
import bisect

n,m = map(int,input().split())
 
city = [[] for _ in range(n+1)]
arr = []
 
for i in range(m):
    s,t = map(int,input().split())
    arr.append((s,t))
 
city =collections.defaultdict(list)

for x,y in sorted(arr):
    city[x] += [y]
for x,y in arr:
    z=str(bisect.bisect(city[x],y))
    print(str(x).rjust(6, "0") + z.rjust(6,"0"))

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

for i in range(1,N+1):
    prefecture[i].sort()
    for j in range(1,len(prefecture[i])+1):
        ans.append([prefecture[i][j-1][1],i,j])
ans.sort()
for i in range(len(ans)):
    print('{:06}{:06}'.format(ans[i][1],ans[i][2]))

Solution (Python):
from operator import itemgetter

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

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

iPY.sort(key=itemgetter(2))

count = [0] * (N + 1)
ans = [''] * M
for ipy in iPY:
    count[ipy[1]] += 1
    ans[ipy[0]] = '{:06}{:06}'.format(ipy[1], count[ipy[1]])

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

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

d = defaultdict(int)
c = {}
for p, y in sorted(l, key=lambda x: x[1]):
  d[p] += 1
  c[y] = str(p).zfill(6) + str(d[p]).zfill(6)

for p, y in l:
  print(c[y])

Solution (Python):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    town[place-1].append([year,i])

ans = []
k = 0
for item in town:
    index = k
    item.sort()
    index = str(index+1)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = str(i+1)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        ans.append([item[i][1],xxx])
    k += 1

ans.sort()
for item in ans:
    print(item[1])

Solution (Python):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    town[place-1].append([year,i])



ans = []
k = 0
for item in town:
    index = k
    
    
    item.sort()
    index = str(index+1)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = str(i+1)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        ans.append([item[i][1],xxx])
    k += 1

ans.sort()
for item in ans:
    print(item[1])